题解：分特产

题解：分特产

问题分析

我们有 \(m\) 种特产，每种特产的数量为 \(a_i\)，需要分给 \(n\) 个同学，每个同学至少得到一个特产。需要计算不同的分配方案数。

关键限制：

1. 每种特产可以分给任意多个同学
2. 同种特产是相同的（不可区分）
3. 不同的同学是可区分的
4. 每个同学必须至少获得一个特产

核心思路：二项式反演

1. 不考虑"每个同学至少一个特产"的限制

对于第 \(i\) 种特产（数量为 \(a_i\)），分给 \(n\) 个同学（允许空手）的方案数为组合数：

\[\binom{a_i + n - 1}{n - 1} \]

这是隔板法的结果。

对于所有 \(m\) 种特产，总方案数为：

\[g(n) = \prod_{i=1}^{m} \binom{a_i + n - 1}{n - 1} \]

其中 \(g(k)\) 表示把特产任意分配给 \(k\) 个同学（允许空手）的方案数。

2. 二项式反演公式

设 \(f(k)\) 表示恰好 \(k\) 个同学得到特产，且每个得到特产的都至少得到一个。

我们要求的是 \(f(n)\)。

考虑任意分配给 \(j\) 个同学的方案数 \(g(j)\)，它与 \(f(k)\) 的关系：

\[g(j) = \sum_{k=0}^{j} \binom{j}{k} f(k) \]

解释：从 \(j\) 个同学中选 \(k\) 个真正得到特产（每个至少一个），剩下 \(j-k\) 个空手。

根据二项式反演：

\[f(j) = \sum_{k=0}^{j} (-1)^{j-k} \binom{j}{k} g(k) \]

特别地，当 \(j=n\) 时：

\[f(n) = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} g(k) \]

3. 代码映射

计算 \(g(k)\)

对于每个 \(k\)（\(1 \le k \le n\)）：

g[k] = 1;
for(int i = 0; i < m; i++) {
    g[k] = g[k] * comb(a[i] + k - 1, k - 1) % MOD;
}

注意 \(k=0\) 时，\(g(0)=0\)（没有同学可分配）。

二项式反演计算 \(f(n)\)

ll ans = 0;
for(int k = 0; k <= n; k++) {
    ll sign = ((n - k) % 2 == 0) ? 1 : -1;
    ll term = comb(n, k) * g[k] % MOD;
    if(sign == -1) term = MOD - term;
    ans = (ans + term) % MOD;
}

完整代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 2010; // n + max(a_i) ≤ 2000

ll fac[MAXN], inv_fac[MAXN];

// 快速幂求逆元
ll qpow(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘和阶乘逆元
void init() {
    fac[0] = 1;
    for(int i = 1; i < MAXN; i++) 
        fac[i] = fac[i-1] * i % MOD;
    
    inv_fac[MAXN-1] = qpow(fac[MAXN-1], MOD-2);
    for(int i = MAXN-2; i >= 0; i--)
        inv_fac[i] = inv_fac[i+1] * (i+1) % MOD;
}

// 组合数 C(n,m)
ll comb(int n, int m) {
    if(n < m || m < 0) return 0;
    return fac[n] * inv_fac[m] % MOD * inv_fac[n-m] % MOD;
}

int main() {
    init();
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(m);
    for(int i = 0; i < m; i++)
        cin >> a[i];
    
    // 计算 g[k] = ∏ C(a[i]+k-1, k-1)
    vector<ll> g(n+1, 0);
    for(int k = 1; k <= n; k++) {
        g[k] = 1;
        for(int i = 0; i < m; i++) {
            g[k] = g[k] * comb(a[i] + k - 1, k - 1) % MOD;
        }
    }
    
    // 二项式反演：f(n) = Σ (-1)^(n-k) * C(n,k) * g(k)
    ll ans = 0;
    for(int k = 0; k <= n; k++) {
        ll sign = ((n - k) % 2 == 0) ? 1 : MOD-1; // (-1)^(n-k)
        ll term = comb(n, k) * g[k] % MOD;
        ans = (ans + sign * term) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}

时间复杂度分析

1. 预处理阶乘：\(O(\text{MAXN})\)，约 \(O(2000)\)
2. 计算 g[k]：\(O(n \times m)\)，最大 \(1000 \times 1000 = 10^6\)
3. 二项式反演求和：\(O(n)\)

总时间复杂度：\(O(n \times m)\)，可以接受。

关键点总结

1. 隔板法计算 \(g(k)\)：每种特产独立，使用组合数 \(\binom{a_i+k-1}{k-1}\)
2. 二项式反演转换：从"允许空手"到"每个至少一个"
3. 组合数预处理：模素数下的组合数通过阶乘和逆元快速计算
4. 符号处理：\((-1)^{n-k}\) 通过奇偶判断实现

示例运行

输入：

5 4
1 3 3 5

计算过程：

1. \(g(1) = \binom{1+0}{0} \times \binom{3+0}{0} \times \binom{3+0}{0} \times \binom{5+0}{0} = 1\)
2. \(g(2) = \binom{1+1}{1} \times \binom{3+1}{1} \times \binom{3+1}{1} \times \binom{5+1}{1} = 2 \times 4 \times 4 \times 6 = 192\)
3. \(g(3) = \cdots = 19440\)
4. \(g(4) = \cdots = 658240\)
5. \(g(5) = \cdots = 11106000\)

应用反演公式：

\[f(5) = \sum_{k=0}^{5} (-1)^{5-k} \binom{5}{k} g(k) = 384835 \]

输出：

384835