题目
题目描述
JYY 带队参加了若干场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
输出描述
输出一行，不同分配方案的总数。由于输出结果可能非常巨大，你只需要输出最终结果MOD 1,000,000,007的数值就可以了。
示例1
输入
5 4
1 3 3 5
输出
384835
题解
知识点：容斥原理，排列组合。
直接分十分困难，因为转化为球盒模型，即球和盒都有区别，但球是一个多重集。
现在，我们考虑每个特产的贡献，如果没有非空限制，那么每种特产就相当于球相同但盒子不相同的情况，我们可以直接隔板法解决，答案为 \(\displaystyle \prod_{i=1}^m \dbinom{n+a_i-1}{a_i}\) 。
如果考虑每个同学都有特产，即非空，那么考虑容斥：所有情况-至少1个同学空+至少2个同学空-... ，这样就得到的就是所有情况-存在同学空的情况 ，即得到所有同学非空。
那么对于有 \(i\) 个同学空的情况，方案数为 \(\displaystyle \binom{n}{i} \cdot \displaystyle \prod_{i=1}^m \dbinom{n-i+a_i-1}{a_i}\) ，选 \(i\) 个同学空剩下的隔板法分配。
时间复杂度 \(O(nm)\)
空间复杂度 \(O(n+m)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
namespace Number_Theory {
const int N = 1e7 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int fact[N], invfact[N];
void init(int n) {
fact[0] = 1;
for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
invfact[n] = qpow(fact[n], P - 2);
for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
}
}
namespace CNM {
using namespace Number_Theory;
int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;
}
}
/// 公式法求组合数，O(n)，预处理阶乘及其逆元快速求出组合数
int a[1007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1;i <= m;i++) cin >> a[i];
Number_Theory::init(2000);
int ans = 0;
for (int i = 0;i <= n;i++) {
int mul = CNM::C(n, i);
for (int j = 1;j <= m;j++) mul = 1LL * mul * CNM::C(a[j] + n - i - 1, a[j]) % P;
(ans += (i & 1 ? -1 : 1) * mul) %= P;
(ans += P) %= P;
}
cout << ans << '\n';
return 0;
}