原题呈现

P5505 分特产#

题目描述#

JYY 带队参加了若干场 $\text{ACM/ICPC}$ 比赛，带回了许多土特产，要分给实验室的同学们．

JYY 想知道，把这些特产分给 $n$ 个同学，一共有多少种不同的分法？当然，JYY 不希望任何一个同学因为没有拿到特产而感到失落，所以每个同学都必须至少分得一个特产．

例如，JYY 带来了 $2$ 袋麻花和 $1$ 袋包子，分给 $A$ 和 $B$ 两位同学，那么共有 $4$ 种不同的分配方法：

$A$ ：麻花， $B$ ：麻花、包子

$A$ ：麻花、麻花， $B$ ：包子

$A$ ：包子， $B$ ：麻花、麻花

$A$ ：麻花、包子， $B$ ：麻花

输入格式#

输入数据：

第一行是同学的数量 $n$ 和特产的种类 $m$ ．

第二行包含 $m$ 个整数，表示每一种特产的数量．

$n, m$ 不超过 $1000$ ，每一种特产的数量不超过 $1000$ ．

输出格式#

输出一行，不同分配方案的总数．

由于输出结果可能非常巨大，你只需要输出最终结果 $\bmod\ {10^9+7}$ 的数值就可以了．

输入输出样例 #1#

输入 #1#

输出 #1#

1
384835

正难则反，我们先抛弃“所以每个同学都必须至少分得一个特产”这一个条件，对于每一种特产，我们需要求将 $a_i$ 个特产分给 $n$ 位同学的方案数，这等同于将 $a_i$ 个没标号的小球放在 $n$ 个标号的盒子里，允许空盒．共有 $\binom{a_i+n-1}{n-1}$ 种可能．由于对于每一种特产都有上述方案，因此总方案数 $a(0)$ 为：

a(0) = \prod^{m}_{i=1} \binom{a_i+n-1}{n-1}

接下来处理空盒的情况．

我们使用容斥，答案为 $T$ 减去钦定任意一个盒子为空的方案数，加上钦定任意两个盒子为空的方案数，减去钦定任意三个盒子为空的方案数，直到所有盒子都为空的方案数．

存在 $k$ 个盒子为空的方案数 $a(k)$ ，可以想象成去掉这 $k$ 个盒子，其他盒子可以为空，也可以不为空，可以使用上面计算 $k=0$ 的方法，因此对于每一种钦定方案所对应的方案数 $a'(k)$ ，有：

a'(k)=\prod^{m}_{i=1} \binom{a_i+n-k-1}{n-k-1}

由于钦定了 $k$ 个盒子为空，这又有 $\binom{n}{k}$ 种钦定方法，所以有：

a(k)=\binom{n}{k} a'(k)

显然，各个约束地位相等，因此根据容斥公式，可以算出答案 $ans$ ，公式如下：

ans = \sum_{k=0}^{n}((-1)^k a(k))

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int N = 2005;
5
const int MOD = 1e9 + 7;
6
int n, m, a[N], C[N][N];
7
int ans;
8
int calC(int x, int y) {
9
    if (x == y || y == 0)
10
        return 1;
11
    if (C[x][y] == 0) {
12
        C[x][y] = (calC(x - 1, y) + calC(x - 1, y - 1)) % MOD;
13
    }
14
    return C[x][y];
15
}
16
signed main() {
17
    cin >> n >> m;
18
    for (int i = 1; i <= m; i++) {
19
        cin >> a[i];
20
    }
21
    for (int i = 0; i < n; i++) {
22
        int tot = 1;
23
        for (int j = 1; j <= m; j++) {
24
            (tot *= calC(n + a[j] - i - 1, n - i - 1)) %= MOD;
25
        }
26
        int coe = calC(n, i);
27
        if (i % 2 == 1)
28
            coe = (MOD - coe) % MOD; // (-1)^i
29
        ans = (ans + coe * tot) % MOD;
30
    }
31
    cout << ans % MOD;
32
}

音乐

音乐

P5505 分特产#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

文章分享

音乐

安吉D4-G

P5505 分特产#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

文章分享