题目链接
Problem Description
世界杯正如火如荼地开展！度度熊来到了一家酒吧。 有 N 对情侣相约一起看世界杯，荧幕前正好有 2×N 个横排的位置。 所有人都会随机坐在某个位置上。 当然，如果某一对情侣正好挨着坐，他们就会有说不完的话，影响世界杯的观看。 一般地，对于一个就座方案，如果正好有 K 对情侣正好是挨着坐的，就会产生 DK 的喧闹值。 度度熊想知道随机就座方案的期望喧闹值。 为了避免输出实数，设答案为 ans，请输出 ans×(2N)! mod P 的值。其中 P=998244353
Input
有多组数据（不超过 1000 组），读到EOF结束。
对于每一组数据，读入两个数 N 和 D 。
1≤N,D≤1000
Output
对于每一组数据，输出一个数表示答案。
Sample intput
1 10
2 3
Sample Output
20
104
题意:
中文题！！！
思路:
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>
using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 998244353;
const int maxn = 1e3 + 10;
LL dp[maxn][maxn],f[maxn];
LL qpow(LL x, LL n){
LL ans = 1;
x = x % mod;
while(n){
if(n&1) ans = ans * x % mod;
x = x * x % mod;
n >>= 1;
}return ans;
}
void init(){
dp[1][1] = 1;
f[0] = 1;
LL inv = qpow(2, mod-2);
f[1] = 2;
for(int i = 2; i < maxn; ++i){
for(int j = 0; j <= i; ++j){
if(j) dp[i][j] += dp[i-1][j-1] * (2*i-j) % mod;
dp[i][j] += dp[i-1][j] * j % mod;
if(j+2 <= i-1) dp[i][j] += dp[i-1][j+2] * ((j+2)*(j+1)%mod *inv % mod) % mod;
if(j+1 <= i-1) dp[i][j] += dp[i-1][j+1] * (2*i-j-2)*(j+1)%mod;
if(i-1 >= j) dp[i][j] += dp[i-1][j] * ((2*i-j-1)*(2*i-j-2) % mod* inv % mod) % mod;
dp[i][j] %= mod;
}f[i] = f[i-1]*2%mod;
}
}
int main(){
init();
int n,d;
while(scanf("%d %d", &n, &d) != EOF){
LL ans = 0;
LL k = 1;
for(int i = 0; i <= n; ++i)
(ans += dp[n][i] * k) %= mod, k=k*d%mod;
printf("%lld\n",ans*f[n] % mod);
}
return 0;
}
|