2021牛客暑期多校训练营4 G、Product

题目大意

给出 $n,k,D$ ，你要构造的序列 $a_i\ge 0,\sum\limits_{i=1}^na_i = D$ ，对于其中一个序列 $a$ 来说他的贡献是 $\displaystyle\frac{D!}{\prod\limits_{i=1}^n(a_i+k)!}$ ，现在要你求出全部可能的 $a$ 序列贡献之和是多少？

$n,k\le50,D\le10^8$

Solution

考点：动态规划+容斥原理+组合数意义

我们首先要推出下面这样的一个式子，可以看出这是 $D$ 个球分成 $n$ 组的可能方案数，那么总的方案数就是 $n^D$ ，即每个球都可能在每一组。

$\sum\limits_{i=1}^na_i = D \ \ \ (a_i\ge 0)\\D!*\prod\limits_{i=1}^n\displaystyle\frac{1}{a_i} = n^D$

好，我们回来看题目给出的式子，我们如果把 $a_i+k$ 看成一个整体带入我们刚刚上面推出的公式我们就会得到这样的式子。

$\sum\limits_{i=1}^na_i = D+nk \ \ \ (a_i\ge 0)\\(D+nk)!*\prod\limits_{i=1}^n\displaystyle\frac{1}{a_i} = n^{D+nk}$

但是很容易发现一个问题就是题目给出的 $a_i$ 范围是 $\ge k$ 的但是我们公式的范围是 $\ge 0$ 的，这就会导致我们直接计算答案的话会出现很多非法的解，那么我们就要考虑把这些非法的解全部去掉，就要用到容斥原理了。

那么我们知道我们一共有 $n$ 组，那么起始 $0$ 组非法的答案减掉有 $1$ 组非法答案的解加上有 $2$ 组非法答案的解 $…$ 直到容斥系数被算完为止，好那么问题就转换为如何求解有 $i$ 组非法答案的解的数量呢？

这个求解就比较容易了，考虑动态规划 $f[i][j]$ 代表对于前 $i$ 组当前有 $j$ 个球要分配而言非法答案的方案数。

我们使用 $O(n)$ 的转移就可以求到这个 $f$ 数组。

$f[0][0] = 1\\\\f_{i,j}=\sum\limits_{s=0}^{k-1}f_{i-1,j-s}*C_j^s$

接下来答案就会是下面这个式子，从前往后依次是计算答案的修正系数，容斥系数，有多少组非法，多少个球非法并且都要计算组合数，最后是剩余组剩余球合法的方案数。

$\displaystyle\frac{D!}{(D+nk)!}\sum\limits_{i=0}^n(-1)^i\sum\limits_{j=0}^{i*(k-1)}f_{i,j}*C_n^i*C_{D+nk}^j*(n-i)^{D+nk-j}$

ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int MOD = 998244353;
const int N = 55 + 7;
ll n, k, D;
int C[N * N][N * N];
int f[N][N * N];

inline int add(int a, int b) {
    if (a + b >= MOD)    return a + b - MOD;
    return a + b;
}

void init() {
    for (int i = 0; i < N * N; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
        }
    }
    f[0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i * (k - 1); ++j)
            for (int s = 0; s <= k - 1; ++s)
                f[i + 1][j + s] = add(f[i + 1][j + s], f[i][j] * C[j + s][s] % MOD);
}

inline int inv(int x) {
    return qpow(x, MOD - 2, MOD);
}

int solve() {
    n = read(), k = read(), D = read();
    init();

    int res = 0;
    for (int i = 0; i <= n; ++i) {
        int jc = 1;
        int sum = 0;
        int pre = (i & 1) ? MOD - C[n][i] : C[n][i];

        for (int j = 0; j <= i * (k - 1); ++j) {
            int tmp = f[i][j] * qpow(n - i, D + n * k - j, MOD) % MOD * jc % MOD;
            sum = add(sum, tmp);
            jc = jc * ((D + n * k - j) % MOD) % MOD * inv(j + 1) % MOD; // D太大了
        }

        res = add(res, sum * pre % MOD);
    }

    for (int i = D + 1; i <= D + n * k; ++i) {
        res = res * inv(i) % MOD;
    }
    print(res);



    return 1;
}