[JSOI2011] 分特产

题意

有 $m$ 种特产，第 $i$ 种有 $a[i]$ 个，同种特产互相不区分。

现在要把这些特产分给 $n$ 个不同同学，并且要求每个同学至少拿到一个特产。
求总方案数，对 $1000000007$ 取模。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 MOD = 1000000007LL;

int n, m;
int a[12];
int sum_get[12];
int give[12][12];
i64 ans;

void dfs_type(int kind);
void dfs_person(int kind, int person, int remain);

// 逐种特产枚举分配方案。
void dfs_type(int kind) {
    if (kind > m) {
        for (int i = 1; i <= n; i++) {
            if (sum_get[i] == 0) {
                return;
            }
        }
        ans++;
        if (ans >= MOD) {
            ans -= MOD;
        }
        return;
    }

    dfs_person(kind, 1, a[kind]);
}

// 枚举第 kind 种特产分给每个同学多少个。
void dfs_person(int kind, int person, int remain) {
    if (person == n) {
        give[kind][person] = remain;
        for (int i = 1; i <= n; i++) {
            sum_get[i] += give[kind][i];
        }

        dfs_type(kind + 1);

        for (int i = 1; i <= n; i++) {
            sum_get[i] -= give[kind][i];
        }
        return;
    }

    for (int x = 0; x <= remain; x++) {
        give[kind][person] = x;
        dfs_person(kind, person + 1, remain - x);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }

    dfs_type(1);
    cout << ans << '\n';

    return 0;
}

这个暴力会按“第几种特产”递归，枚举这一种特产分别给每个同学多少个，最后检查有没有同学一个都没拿到。它能帮助理解题意，也适合小数据对拍。

正式做法要先把问题拆开看。

如果暂时不要求“每个同学至少一个”，那么对一种数量为 $a[i]$ 的特产：

它是 $a[i]$ 个相同物品
要分给 $n$ 个不同同学
允许某些同学拿 $0$ 个

按隔板法，方案数就是：

$C(a[i] + n - 1, n - 1)$

而不同种特产彼此独立，所以不加限制时的总方案数就是这些值的乘积。

真正难的是“不能有空同学”。这时可以直接做容斥：

枚举有多少个同学空着，记为 $t$
先选出这 $t$ 个空同学： $C(n,t)$
剩下 $n-t$ 个同学接收所有特产

于是对单种特产，方案数变成：

$C(a[i] + n-t - 1, n-t - 1)$

所以总答案就是：

$\sum_{t=0}^{n-1} (-1)^t C(n,t) \prod_{i=1}^{m} C(a[i] + n-t-1, n-t-1)$

单种特产在固定容斥层里的意义

这张表展示固定 $t$ 后，一种特产该怎么数：

量	含义
$t$	空着的同学数
$n-t$	真正接收特产的同学数
$a[i]$	第 $i$ 种特产的数量
$C(a[i] + n-t - 1, n-t - 1)$	这 $a[i]$ 个相同物品分给 $n-t$ 个不同同学的方案数

把所有种类的贡献乘起来，再乘 $C(n,t)$ 和容斥符号，就得到这一层的总贡献。

代码

cpp

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXN = 1005;
const int MAXV = 3005;
const i64 MOD = 1000000007LL;

int n, m;
int a[MAXN];
i64 fact[MAXV], inv_fact[MAXV];

i64 quick_pow(i64 base, i64 exp) {
    i64 ans = 1;
    base %= MOD;

    while (exp > 0) {
        if (exp & 1) {
            ans = ans * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }

    return ans;
}

void init_comb(int up) {
    fact[0] = 1;
    for (int i = 1; i <= up; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    inv_fact[up] = quick_pow(fact[up], MOD - 2);
    for (int i = up; i >= 1; i--) {
        inv_fact[i - 1] = inv_fact[i] * i % MOD;
    }
}

i64 C(int x, int y) {
    if (y < 0 || y > x) {
        return 0;
    }
    return fact[x] * inv_fact[y] % MOD * inv_fact[x - y] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    int max_a = 0;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        max_a = max(max_a, a[i]);
    }

    init_comb(n + max_a);

    i64 ans = 0;

    // 容斥：先允许有人没分到东西，再把“至少一个人空着”的方案扣掉。
    // 如果恰好有 t 个人空着，那么只剩 n-t 个同学要接收所有特产。
    // 对于一种数量为 a[i] 的特产，把 a[i] 个相同物品分给 n-t 个不同同学，
    // 允许有人分到 0 个，方案数是 C(a[i] + n-t - 1, n-t - 1)。
    for (int empty_cnt = 0; empty_cnt <= n - 1; empty_cnt++) {
        int used = n - empty_cnt;
        i64 ways = C(n, empty_cnt);

        for (int i = 1; i <= m; i++) {
            ways = ways * C(a[i] + used - 1, used - 1) % MOD;
        }

        if (empty_cnt & 1) {
            ans -= ways;
            if (ans < 0) {
                ans += MOD;
            }
        }
        else {
            ans += ways;
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

预处理组合数： $O(n + \max(a[i]))$
枚举容斥层并乘全部特产贡献： $O(nm)$
空间复杂度： $O(n + \max(a[i]))$

总结

这题的关键有两步：

把单种特产的分法识别成隔板法
把“每个同学至少一个”改成“哪些同学空着”，再做容斥

一旦这两步想通，整题就是很标准的“组合数乘积 + 容斥”模型。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

单种特产在固定容斥层里的意义

代码

复杂度

总结

一图流解析