定义
集合
两个集合的交集：集合 \(A\) 与 \(B\) 的交集可以表示为：
\[A \cap B=\{x:x \in A \land x \in B\} \]两个集合的并集：集合 \(A\) 与 \(B\) 的并集可以表示为：
\[A \cup B = \{x:x \in A \lor x \in B \} \]两个集合的差集：集合 \(A\) 与 \(B\) 的差集可以表示为：
\[A - B = \{x:x \in A \land x \not\in B \} \]一个集合的大小：集合 \(A\) 的大小可以表示为：
\[|A| \]容斥原理
定义：
\[|\bigcup_{i=1}^nA_i|=\sum_{j=1}^n(-1)^{j-1}\sum_{a_k\not=a_ {k+1}}\bigcap_{l=1}^mA_{a_i}\]（算式来自 oi-wiki）
其实这个算式并没有太多意义，重点还是要发现一道题是否要用容斥原理以及怎么用
例题
P1450 [HAOI2008] 硬币购物
思路:
这道题的重点在于如何转换为容斥原理，我们把每一种使得最终和为 \(s\) 的方案（没有数量限制）看作一个元素，则假设有所有方案的集合为 \(S\)，而方案中第 \(i\) 种硬币数量超出 \(d_i\) 的所有方案的集合为 \(A_i\)，则我们需要求的答案其实就是：
\[|S|-|\bigcup_{i=1}^4A_i| \]那么该如何的去求出 \(|S|\) 与 \(|\bigcup_{i=1}^4A_i|\) 呢？
首先我们设 \(dp_i\) 表示硬币数量不受限制，最终和为 \(i\) 的方法数，这很明显是一个完全背包，由于题目中 \(s \le 10^5\) ，所以直接预处理即可，这样 \(|S|\) 就是 \(dp_s\)。
void init() {
dp[0] = 1;
for (int i = 1; i <= 4; i++) {
for (int j = c[i]; j <= 100000; j++)
dp[j] += dp[j - c[i]];
}
}
考虑如何求 \(|A_i|\)，我们可以先取 \(d_i+1\) 个 \(i\) 种硬币，那么还剩下 \(s-(d_i+1) \times c_i\) 的金额，再怎么取 \(i\) 的数量肯定超出限制，于是方法数即为 \(dp_{s-(d_i+1) \times c_i}\)，然后就求出了 \(|A_i|\)
同理，如果 \(i\) 与 \(j\) 都超出了限制，你们方法数也应该为 \(dp_{s-(d_i + 1) \times c_i - (d_j+1) \times c_j}\) ，三个或四个的以此类推。
这很明显是一个容斥，于是直接根据容斥原理算，只用枚举每次是哪几类超出限制即可，复杂度 \(O(2^4n)=O(16n)=O(n)\)。
如果这题物品种类有 \(m\) 个，复杂度就是 \(O(n2^m)\)。
code
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int c[5] = {0}, n;
int d[5] = {0}, s;
long long dp[100005] = {0};
bool f[5] = {false};
long long cal() {
int cnt = 0;
long long sum = 0;
for (int i = 1; i <= 4; i++)
if (f[i])
cnt++, sum += (d[i] + 1) * c[i];
if (s < sum)
return 0;
return (cnt % 2 == 1 ? 1ll : (cnt == 0 ? 0 : -1ll)) * dp[s - sum];
}
long long dfs(int k) {
if (k > 4)
return cal();
long long ans = 0;
f[k] = true;
ans += dfs(k + 1);
f[k] = false;
ans += dfs(k + 1);
return ans;
}
void solve() {
for (int i = 1; i <= 4; i++)
cin >> d[i];
cin >> s;
memset(f, false, sizeof f);
cout << dp[s] - dfs(1) << endl;
}
void init() {
dp[0] = 1;
for (int i = 1; i <= 4; i++)
for (int j = c[i]; j <= 100000; j++)
dp[j] += dp[j - c[i]];
}
int main() {
for (int i = 1; i <= 4; i++)
cin >> c[i];
cin >> n;
init();
while (n--)
solve();
return 0;
}
P5505 [JSOI2011]分特产
题目链接：P5505 [JSOI2011]分特产
思路：
这道题的重点以人为单位来计数。
首先说一下可重组合，即把 \(n\) 分成 \(m\) 个非负整数集合，它们的和为 \(n\) 的方法数，我们用小学奥数的挡板法即可得到答案是：\(C_{n+(m-1)}^{m-1}\)。
我们设 \(T_{i,k}\) 表示把第 \(i\) 种特产，数量为 \(a_i\)，分给 \(k\) 个人的方法数（不一定每个人都要分到）。这个问题和上面其实是同一个问题，所以 \(T_{i,k}=C_{a_i+(k-1)}^{k-1}\)。
设 \(N_k\) 为把所有特产分给 \(k\) 个人的方法数（依然有人可能没拿到），因为每个特产都要被分发，且第 \(i\) 种特产分给 \(n\) 个人的方法数是 \(T_{i,n}\)，所以这是一个乘法原理，即：
\[N_k=\prod_{i=1}^mT_{i,k} \]设集合 \(A_i\) 为第 \(i\) 名同学没有被分到特产的所有方案的集合，\(S\) 为所有人分所有特产（有人可以没分到）的方案的集合，因为我们要保证每个人都被分到，所以我们要求的就是：\(|S|-|\bigcup\limits_{i=1}^nA_i|\)。
很明显 \(|S| = N_n\)，考虑如何求 \(|\bigcup\limits_{i=1}^nA_i|\)。我们先考虑如果某一个同学没拿到特产的方法数（别的也不一定都拿到）应该为 \(N_{n-1}\)，因为有 \(n\) 个人，所以总共是： \(C_n^1 \times N_{n-1}\)。在考虑有两个人没拿到特产的方法数，总共应该是 \(C_n^2 \times N_{n-2}\)，而上面这两者是有交集的，于是根据容斥原理，我们可以以此类推，得到：
\[|\bigcup\limits_{i=1}^nA_i|=\sum_{i=1}^n(-1)^{i+1}C_n^i\times N_{n-i} \]所以答案其实就是：
\[\sum_{i=0}^n(-1)^{i}C_n^i\times N_{n-i} \]然后就快乐的 AC 了~~
code
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 1000;
int fpow(int a, int b, int p) {
if (b == 0)
return 1;
int ans = fpow(a, b / 2, p);
ans = (1ll * ans * ans) % p;
if (b % 2 == 1)
ans = (1ll * ans * a) % p;
return ans;
}
int fac[2 * MAXN + 5] = {0}, inv[2 * MAXN + 5] = {0};
void init() {
fac[0] = 1;
for (int i = 1; i <= 2000; i++)
fac[i] = (1ll * fac[i - 1] * i) % mod;
inv[2000] = fpow(fac[2000], mod - 2, mod);
for (int i = 1999; i >= 0; i--)
inv[i] = (1ll * inv[i + 1] * (i + 1)) % mod;
}
int cmb(int n, int m) {//从n个数中选m个
return (1ll * (1ll * fac[n] * inv[m]) % mod * inv[n - m]) % mod;
}
int rep(int n, int m) {//把n个物体分给m个人
return cmb(n + (m - 1), m - 1);
}
int n, m;
int a[MAXN + 5] = {0};
int N[MAXN + 5] = {0};
int main() {
init();
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> a[i];
for (int i = 1; i <= n; i++) {
N[i] = 1;
for (int j = 1; j <= m; j++)
N[i] = (1ll * rep(a[j], i) * N[i]) % mod;
}
int ans = N[n];
for (int i = 1; i <= n; i++)
if (i % 2 == 1)
ans = (ans + mod - (1ll * cmb(n, i) * N[n - i]) % mod) % mod;
else
ans = (ans + mod + (1ll * cmb(n, i) * N[n - i]) % mod) % mod;
cout << ans << endl;
return 0;
}
P6076 [JSOI2015]染色问题
题目链接：P6076 [JSOI2015]染色问题
思路：
设 \(T_i\) 为有 \(i\) 种颜色确定不用，剩下的颜色随意的方法数，则根据容斥原理，我们要求的就是：
\[\sum_{i=0}^n(-1)^i\times C_n^i \times T_i \]考虑如何求 \(T_k\)。我们记 \(N_i\) 为有 \(i\) 行确定不涂色，其他行随意的，但是每一列都有颜色的方法数，则根据容斥原理，很明显：
\[T_k = \sum_{i=0}^n(-1)^i\times C_n^i\times N_i \]考虑如何求 \(N_i\)（别烦，这时最后一个了）。我们考虑把每一列拆开来，因为每一列有 \(n-i\) 个格子需要染色，每个格子有 \(c-k+1\) 种染色方法（不染色也算一种），所以对于一列来说，共有 \((c-k+1)^{n-i}\) 种染色方式，但是不能全部不染色，所以还要减去一，即 \((c-k+1)^{n-i}-1\)。因为总共有 \(m\) 列，并且每一列是相互独立的，于是就知道了：
\[N_i = [(c-k+1)^{n-i}-1]^m \]然后就可以求出 \(T_k\)，最后求出答案了。
在具体实现中，其实并不需要去真的开三个数组。这题除了求组合数时阶乘以及逆元需要开个数组，其他都没必要。
代码很简单，但其实思维难度还是很高的。
code
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 1000;
int fpow(int a, int b, int p) {
if (b == 0)
return 1;
int ans = fpow(a, b / 2, p);
ans = (1ll * ans * ans) % p;
if (b % 2 == 1)
ans = (1ll * ans * a) % p;
return ans;
}
int fac[2 * MAXN + 5] = {0}, inv[2 * MAXN + 5] = {0};
void init() {
fac[0] = 1;
for (int i = 1; i <= 2000; i++)
fac[i] = (1ll * fac[i - 1] * i) % mod;
inv[2000] = fpow(fac[2000], mod - 2, mod);
for (int i = 1999; i >= 0; i--)
inv[i] = (1ll * inv[i + 1] * (i + 1)) % mod;
}
int cmb(int n, int m) {
return (1ll * (1ll * fac[n] * inv[m]) % mod * inv[n - m]) % mod;
}
int n, m, c;
int cal(int k) {
int ans = 0;
for (int i = 0; i <= n; i++)
if (i % 2 == 0)
ans = (ans + mod + (1ll * cmb(n, i) * fpow(fpow(c - k + 1, n - i, mod) - 1, m, mod) % mod)) % mod;
else
ans = (ans + mod - (1ll * cmb(n, i) * fpow(fpow(c - k + 1, n - i, mod) - 1, m, mod) % mod)) % mod;
return ans;
}
int main() {
init();
cin >> n >> m >> c;
int ans = 0;
for (int i = 0; i <= c; i++)
if (i % 2 == 0)
ans = (ans + mod + (1ll * cmb(c, i) * cal(i)) % mod) % mod;
else
ans = (ans + mod - (1ll * cmb(c, i) * cal(i)) % mod) % mod;
cout << ans << endl;
return 0;
}