鄙人最不欣赏的类型的题（
来考虑一个正常人考虑不到的二元生成函数 \[ F(x,y) = \prod\limits_{i=1}^M \left[p_i \frac{ 1 - (xy)^{a_i+1} }{1-xy} + (1-p_i) \frac{ 1 - x^{a_i+1} }{1-x}\right] \]
那么答案即为 \[ \sum\limits_{k \ge n} [x^N y^k] F(x,y) \]
考虑对于 \(i,j,k\) 计算出 \[\frac{ x^{id} y^{jd} }{ (1-xy)^{M-k} (1-x)^k }\]
在 \(F(x,y)\) 展开式中的系数，然后对于每个这样的项分别提取需要的系数。
那么问题变成对于若干组 \(A,B,C,D\) 计算 \[ \sum\limits_{k \ge D} [x^C y^k] \frac 1{(1-xy)^A(1-x)^B} \]
联想到一般的形如 \(\frac1{(1-x)^A}\) 的生成函数的系数，考虑将其作为隔板处理。
直接枚举 \(i\) 表示 \(i\) 为第一个在 \(D\) 之后的隔板，有答案等于 \[
\sum\limits_{i=1}^A \binom{D+i-1}i \binom{m-i+c-d}{m-i}
\]
简单地 \(O(A)\) 递推出组合数，直接计算即可。
复杂度 \(O\left(\frac{N^2M^2}{d^2}\right)\)。
代码： 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
using namespace std;
const int M = 100;
const int mod = 998244353;
int m,d,N,n;
int inv[M + 5];
int a[M + 5],c[M + 5],p[M + 5];
int f[M + 5][M + 5][M + 5][M + 5];
int C[2][M + 5];
int ans,s;
int main()
{
freopen("key.in","r",stdin),freopen("key.out","w",stdout);
scanf("%d%d%d%d",&m,&d,&N,&n),inv[1] = 1;
for(register int i = 2;i <= M;++i)
inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
for(register int i = 1;i <= m;++i)
scanf("%d%d",a + i,p + i),c[i] = (a[i] + 1) / d;
f[0][0][0][0] = 1;
for(register int i = 1;i <= m;++i)
for(register int x = 0;x * d <= N;++x)
for(register int y = 0;y * d <= N;++y)
for(register int z = 0;z < i;++z)
f[i][x][y][z] = (f[i][x][y][z] + (long long)f[i - 1][x][y][z] * p[i]) % mod,
(x + c[i]) * d <= N && (y + c[i]) * d <= N && (f[i][x + c[i]][y + c[i]][z] = (f[i][x + c[i]][y + c[i]][z] - (long long)f[i - 1][x][y][z] * p[i] % mod + mod) % mod),
f[i][x][y][z + 1] = (f[i][x][y][z + 1] + (long long)f[i - 1][x][y][z] * (1 - p[i] + mod)) % mod,
(x + c[i]) * d <= N && (f[i][x + c[i]][y][z + 1] = (f[i][x + c[i]][y][z + 1] - (long long)f[i - 1][x][y][z] * (1 - p[i] + mod) % mod + mod) % mod);
for(register int x = 0;x * d <= N;++x)
for(register int y = 0;y * d <= N;++y)
for(register int z = 0;z <= m;++z)
{
int a = N - x * d,b = max(n - y * d,0);
if(a < b || !f[m][x][y][z])
continue;
C[0][1] = 1;
for(register int i = 2;i <= m - z;++i)
C[0][i] = (long long)C[0][i - 1] * (b + i - 2) % mod * inv[i - 1] % mod;
C[1][m - z] = 1;
for(register int i = 1;i <= z;++i)
C[1][m - z] = (long long)C[1][m - z] * (z + a - b - i + 1) % mod * inv[i] % mod;
for(register int i = m - z - 1;~i;--i)
C[1][i] = (long long)C[1][i + 1] * (m - i + a - b) % mod * inv[m - i] % mod;
s = 0;
for(register int i = 1;i <= m - z;++i)
s = (s + (long long)C[0][i] * C[1][i]) % mod;
ans = (ans + (long long)s * f[m][x][y][z]) % mod;
}
printf("%d\n",ans);
}