题解 [Dwango Programming Contest 6th C] Cookie Distribution

· · 题解

题意概述

有 N 个孩子，用 K 天给孩子们发糖果。

第 i 天有 a_i 个糖果，等概率地发给这 n 个孩子(每一天每个孩子最多可以获得一个糖果)，设 K 天后第 i 个孩子获得的糖果为 c_i。

求 \prod_{i = 1}^n c_i 的期望乘上 \prod_{i = 1}^n \binom N {a_i} ，答案对 10^9 + 7 取模。

N \le 10^3, K \le 20

正解

期望乘上那个组合数就是所有方案下的答案了对吧。

直接 dp 肯定不太好做，要记录每一个人选了多少个曲奇，考虑换一种方式来表示原问题。

首先原问题可以转化成这样一个问题：

"每一个人从拥有的曲奇里选择某一天得到的那一个曲奇， 求不同的选法"

答案其实也正好是 \prod c_i (神奇的是这样做与原问题是等价的)。

所以我们只需要关心每个人选择的那个曲奇就好了。

设 x_i 表示有 x_i 个孩子在第 i 天得到了它们选择的曲奇。

先不考虑顺序, 钦定就是前面 x_i 个人得到了这 x_i 个曲奇。

转移系数是 \binom {N - x_i} {a_i - x_i} (将剩下还没被选的曲奇随便分给其他人)。

最后再将人排序, 乘上 \frac {N!} {\prod x_i!} (同一天选的与顺序没有关系, 所以要除 x_i!)。

答案其实就是：

N! \prod_{i = 1}^n \frac {\binom {N - x_i} {a_i - x_i}} {x_i!}

根据这个式子可以设出状态 f(i, j) 表示前 i 天有 j 个人得到了选择的那个曲奇的方案数。

转移时枚举 x_i 并乘上有关于 x_i 的系数。

状态 O(NK)， 转移 O(N)， 时间复杂度 O(N^2 K)。

\color {DeepSkyBlue} {Code} 
/*
    f[i][j] = \sum f[i - 1][j - x] * comb(n - x, a[i] - x) * ifac[x]
*/
#include <bits/stdc++.h>
#define K 25
#define N 1005

using namespace std;

const int mod = 1e9 + 7;

int n, k;
int a[K], f[K][N];
int fac[N], ifac[N];

inline int fpm(int x, int y) {
    int r = 1;
    while(y) {
        if(y & 1) r = 1LL * r * x % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return r;
}
inline int perm(int x, int y) { return 1LL * fac[x] * ifac[x - y] % mod; }
inline int comb(int x, int y) { return 1LL * perm(x, y) * ifac[y] % mod; }

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= k; ++i)
        scanf("%d", &a[i]);

    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = 1LL * i * fac[i - 1] % mod;
    ifac[n] = fpm(fac[n], mod - 2);
    for(int i = n; i; --i) ifac[i - 1] = 1LL * i * ifac[i] % mod;

    f[0][0] = 1;
    for(int i = 0; i < k; ++i) {
        for(int j = 0; j <= n; ++j) {
            if(!f[i][j]) continue;
            for(int x = 0; x <= a[i + 1] && j + x <= n; ++x) {
                f[i + 1][j + x] = (f[i + 1][j + x] + 
                1LL * f[i][j] * comb(n - x, a[i + 1] - x) % mod * ifac[x]) % mod;
            }
        }
    }

    int ans = 1LL * fac[n] * f[k][n] % mod;
    printf("%d\n", ans);
    return 0;
}