这完全是能力范围内的题。日常做题时还是要多想一想，多尝试尝试，多用几种不同的解法，因为考场上没有看题解的机会。
首先这题看上去就很
容斥，先套上去试一下。
。
考虑一个
该怎么算。
首先， 内的问题无法完全与
外的独立开来，因为每次操作是在所有数之间进行的，这会涉及到一个条件概率的问题。
这里有一个比较巧妙的转化，即 第一次到达停止状态的时间是
所有到达停止状态之前的状态的概率乘上停留在该状态的期望时间
之和（我们熟知的等式 就是在所有状态的期望停留时间均为 时的特例）。
证明并不难，也与
的证明基本一致。（不过这一点倒是增进了我对这个式子的理解）。
那么每个状态的期望停留时间怎么算？
考虑什么时候会“停留”，即我们一次操作选到了集合 之外的点。
显然这个量只与 有关。
更具体地，设 表示集合 中某个状态的期望停留时间，设 ，那么会有 ，即 。
考察另外一个部分，即到达某个状态的概率，设 表示 在该状态中的出现次数。
那么概率就是 设 。
那么将上式化简可得 。
代入
的式子，那么原式可化为
中间两个分式只与 和 有关，而后面的 显然可以 DP。
设 表示考察前 个数， 且 的 之和，转移如下：
。
因为第二维是个背包状物，故直接枚举 就可以做到 了。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 4e2 + 5,P = 998244353;
int n;
int a[N],b[N];
int fac[N],ifac[N];
int f[N][N][N];
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
inline void Minus(int &x,const int &y) { x -= y;if(x < 0) x += P;}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
inline void init(int n)
{
fac[0] = 1;
for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[1] = 1;
for(int i = 2;i <= n;i++) ifac[i] = 1ll * (P - P / i) * ifac[P % i] % P;
ifac[0] = 1;
for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % P;
}
int sumA = 0,sumB = 0;
int main()
{
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i] >> b[i],sumA += a[i],sumB += b[i];
init(sumB);
int sum = 0;
f[0][0][0] = P - 1;
for(int i = 1;i <= n;i++)
{
for(int j = a[i];j <= sumA;j++)
{
for(int k = 0;k <= sum;k++)
for(int c = 0,now = 1;c < b[i];++c)
{
Minus(f[i][j][k + c],1ll * f[i - 1][j - a[i]][k] * now % P * ifac[c] % P);
now = 1ll * now * a[i] % P;
}
}
sum += b[i];
for(int j = 0;j <= sumA;j++)
for(int k = 0;k <= sum;k++)
Plus(f[i][j][k],f[i - 1][j][k]);
}
int ans = 0;
for(int sa = 0;sa <= sumA;sa++)
for(int sc = 0;sc <= sumB;sc++)
Plus(ans,1ll * fac[sc] * sumA % P * qpow(qpow(sa,P - 2),sc+1) % P * f[n][sa][sc] % P);
cout << ans << endl;
return 0;
}
|