JZOJ 6927 張士超你昨天晚上到底把我家鑰匙放在哪了？

鄙人最不欣赏的类型的题（

来考虑一个正常人考虑不到的二元生成函数 F(x,y)=M∏i=1[pi1−(xy)ai+11−xy+(1−pi)1−xai+11−x]

那么答案即为 ∑k≥n[xNyk]F(x,y)

考虑对于 i,j,k 计算出 xidyjd(1−xy)M−k(1−x)k

在 F(x,y) 展开式中的系数，然后对于每个这样的项分别提取需要的系数。

那么问题变成对于若干组 A,B,C,D 计算 ∑k≥D[xCyk]1(1−xy)A(1−x)B

联想到一般的形如 1(1−x)A 的生成函数的系数，考虑将其作为隔板处理。
直接枚举 i 表示 i 为第一个在 D 之后的隔板，有答案等于 A∑i=1(D+i−1i)(m−i+c−dm−i)

简单地 O(A) 递推出组合数，直接计算即可。
复杂度 O(N2M2d2)。

代码：

#include <cstdio>
#include <algorithm>
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);
}