【组合数学】二项式相关与容斥
_Kamisato_Ayaka_
·
2025-01-01 20:40:33
·
算法·理论
二项式定理
(a + b)^n = \displaystyle\sum^{n}_{i=0}{\binom{n}{i}a^ib^{n-i}}
证明:
数学方法。
(a + b) ^ n = a \times (a + b) ^ {n - 1} = a \times b \times (a + b) ^ {n - 2} = \dots
假设我们选了 k 个 a ,我们就需要选 n - k 个 b ,根据乘法原理,可以得到 a^k b^{n-k} ,由于每次是 n 选 k 个 a ,故得到 \binom{n}{k} ,最终加和求得。
证毕。
其中 \binom{n}{i} 为二项式系数。
特殊情况
令 a = -1, b = 1 ,得到:
(1 + (-1)) ^ n = \displaystyle\sum^{n}_{i=0}{(-1)^n\binom{n}{i}}
当 n = 0 时:
\binom{0}{0}(-1)^0 = 1
因此得出:
\displaystyle\sum^{n}_{i=0}{(-1)^n\binom{n}{i}} = [n = 0]
其中方括号为艾弗森括号。
常用的二项式推论
\binom{n}{m} = \binom{n}{m - 1} + \binom{n - 1}{m - 1}\\ \ \\ \binom{n}{m} = \frac{n}{m}\binom{n - 1}{m - 1} \\ \ \\ \binom{n}{i}\binom{i}{j} = \binom{n}{j}\binom{n - j}{i - j} (i,j \leq n) \\ \ \\ \displaystyle\sum^n_{i=0}{\binom{n}{i}} = 2^n \\ \ \\ \displaystyle\sum^m_{i=0}\binom{n}{i}\binom{m}{k - i} = \binom{n + m}{k}
容斥
容斥,说人话,即为在统计方案数出现重复计数的情况时,我们需要使用容斥求解。
简单容斥
已知集合 \left|S_1\right|,\left|S_2\right| ,求 \left| S_1 \cup S_2 \right| 。
最简单的容斥,只需要减去它们之间重叠的部分即可。
\left|{S_1 \cup S_2}\right| = \left| S_1 \right| + \left| S_2 \right| - \left|{S_1 \cap S_2}\right|
若已知集合 \left|S_1\right|,\left|S_2\right|, \left|S_3\right| ,求 \left|{S_1 \cup S_2 \cup S_3}\right| 。
可以用韦恩图求解。
\left|{S_1 \cup S_2 \cup S_3}\right| = \left| S_1 \right| + \left| S_2 \right| + \left| S_3 \right| - \left| S_1 \cap S_2 \right| - \left| S_1 \cap S_3 \right| - \left| S_2 \cap S_3 \right| + \left| S_1 \cap S_2 \cap S_3 \right|
对于更多集合的容斥:
\begin{aligned}
\left|{\mathop{\cup}\limits^{n}_{i=1}{S_i}}\right| &= \displaystyle\sum^{n}_{i=1}{\left|{S_i}\right|} - \displaystyle\sum_{1\leq i < j \leq n}{\left|{S_i \cap S_j}\right|} + \displaystyle\sum_{1 \leq i < j < k \leq n}{\left|{S_i \cap S_j \cap S_k}\right|} - \dots + (-1)^{n-1}{\displaystyle\sum^n_{i=1}\left|{\mathop{\cap}\limits_{i=1}^{n}{{S_i}}}\right|} \\ &= \displaystyle\sum^{n}_{i=1}{(-1)^{i-1}\displaystyle\sum_{a_i < a_{i+1}}\left|{\mathop{\cap}\limits_{i=1}^{n}{S_{a_i}}}\right|}
\end{aligned}
二项式反演
在已知函数 f_n 与 g_n 存在特定关系,即 f_n 为 n 项物品构成特定结构的方案数,g_n 为从 n 中选出 i \geq 0 项物品构成特殊结构的方案数,在已知 f_n 的情况下我们很容易可以得到:
g_n = \displaystyle\sum^n_{i=0}{\binom{n}{i}f_n}
那如果我们只知道 g_n 呢?
考虑递推,从 1 项物品推到 n 项物品,显然的我们会发现有情况会算重,因此需要带容斥系数。
f_n = \displaystyle\sum_{i=1}^{n}{(-1)^{n-i}\binom{n}{i}g_i}
对于这种特殊关系:当题目中出现恰好需要 n 项物品构成特殊结构的方案数,可以转换成 f_n 表示恰好需要 n 项物品构成特殊结构的方案数,g_n 表示至少 / 至多需要 n 项物品构成特殊结构的方案数,题目中出现至少 / 至多需要亦可与恰好一起考虑。
例题
P10596 BZOJ2839 集合计数
记 f_i 表示集合交集元素恰为 i 的方案数,g_i 表示选出 j 个子集交集元素为 i 的方案数,发现它们满足二项式反演的关系,即 f_i 是 i 个不同元素构成特定结构的方案数时 g_i 是从 i 个中选出 j \geq 0 个构成特定结构的方案数,f_k 即为我们想要的答案,得到以下柿子:
g_n = \displaystyle\sum_{i=0}^{n}{\binom{n}{i}f_i}
\\
\downarrow
\\
f_n = \displaystyle\sum_{i=0}^{n}{(-1)^{n-i}\binom{n}{i}g_i}
所以推出 f_k 的柿子,但是在 n - k 中取会算重,所以应该是取至少 k ,得到:
f_k = \displaystyle\sum^{n}_{i=k}{(-1)^{i-k}\binom{i}{k}g_i}
在剩下 n - k 个中,选的方案数 \binom{n}{i} ,任意选或不选,方案数是 2^{n-k} ,再从这些集合中选出若干个非空集合方案数是 2^{2^{n-k}} - 1 ,得到 g_k :
g_k = \displaystyle\sum^{n}_{i=k}{\binom{n}{i} \cdot (2^{2^{n-i}} - 1)}
答案就是 g_k 。
参考代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 10, mod = 1e9 + 7;
int n, k, fac[maxn], invfac[maxn], g[maxn];
void write (__int128_t x) {
if (x > 9) write (x / 10);
if (x < 0) x = -x, putchar ('-');
putchar (x % 10 + '0');
}
inline int binpow (int x, int k, int mod) {
int ret = 1;
while (k) {
if (k & 1) ret = ret * x % mod;
x = x * x % mod;
k >>= 1;
}
return ret;
}
inline void getFac() {
fac[0] = 1;
for (int i = 1; i <= 1e6; i ++)
fac[i] = fac[i - 1] * i % mod;
invfac[1000000] = binpow (fac[1000000], mod - 2, mod);
for (int i = 999999; i >= 0; i --)
invfac[i] = invfac[i + 1] * (i + 1) % mod;
return;
}
inline int Com (int n, int m) {
if (n < 0 || m < 0 || m > n) return 0;
return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
inline void Solve() {
__int128_t Answer = 0;
for (int i = k; i <= n; i ++) {
int tmp = binpow (2, n - i, mod - 1);
g[i] = Com (n, i) % mod * (binpow (2, tmp, mod) - 1) % mod;
}
for (int i = k; i <= n; i ++)
Answer = (Answer + (((i - k) & 1) ? -1 : 1) * Com (i, k) % mod * g[i] % mod + mod) % mod;
write (Answer), putchar ('\n');
return;
}
signed main() {
scanf ("%lld %lld", &n, &k);
getFac(), Solve();
return 0;
}
CF1400G Mercenaries
区间的处理可以开桶差分,注意到 m \leq 20 ,考虑状压,对于一个状态 st ,它在二进制下当前位为 1 表示需要选当前位,0 反之,然后就是容斥:至少 0 个 1 - 至少 1 个 1 + 至少 2 个 1 \cdots ,以上均讨论方案数。
接着是动规,记 dp_{i,j} 表示前 i 个选 j 人出征的方案,转移方程:
dp_{i,j} = \displaystyle\sum^{2m}_{j=0}{dp_{i-1,j} + \binom{t_i - j}{i - j}}
接着找到对于冲突的 $a_i,b_i$ 的最大 $l$ 和最小 $r$,答案:
$$
\displaystyle\sum^{2^m - 1}_{st=0}{(-1)^{\operatorname{popcount}(st)} \times (dp_{mnr,tmpCnt} - dp_{mxl - 1, tmpCnt})}
$$
其中 $tmpCnt$ 为开桶统计的出现的不同的人的个数。
参考代码:
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 10, mod = 998244353;
int n, m, buck[maxn], dp[maxn][50], fac[maxn], invfac[maxn], tmpArr[maxn], mxp, mnp, tmpCnt, Answer;
struct Ayaka { int x, y; } sol[maxn], sat[25];
inline int binpow (int x, int k) {
int ret = 1;
while (k) {
if (k & 1) ret = ret * x % mod;
x = x * x % mod;
k >>= 1;
}
return ret;
}
inline void Getfac() {
fac[0] = invfac[0] = 1;
for (int i = 1; i <= 3e5; i ++)
fac[i] = fac[i - 1] * i % mod;
invfac[300000] = binpow (fac[300000], mod - 2);
for (int i = 299999; i >= 1; i --)
invfac[i] = invfac[i + 1] * (i + 1) % mod;
return;
}
inline int Com (int n, int m) {
if (n < 0 || m < 0 || m > n) return 0;
return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
inline int popcount (int st) {
int tmpCnt = 0;
while (st) {
tmpCnt += (st % 2 ? 1 : 0);
st /= 2;
}
return tmpCnt;
}
signed main() {
scanf ("%lld %lld", &n, &m), Getfac();
for (int i = 1; i <= n; i ++) {
scanf ("%lld %lld", &sol[i].x, &sol[i].y);
buck[sol[i].x] ++, buck[sol[i].y + 1] --;
}
for (int i = 1; i <= n; i ++)
buck[i] += buck[i - 1];
for (int i = 1; i <= m; i ++)
scanf ("%lld %lld", &sat[i].x, &sat[i].y);
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= (m << 1); j ++)
dp[i][j] = (dp[i - 1][j] + Com (buck[i] - j, i - j)) % mod;
}
for (int st = 0; st < (1 << m); st ++) {
mxp = 1, mnp = n, tmpCnt = 0;
for (int i = 1; i <= m; i ++) {
if ((st >> (i - 1)) & 1) {
mxp = max (mxp, max (sol[sat[i].x].x, sol[sat[i].y].x));
mnp = min (mnp, min (sol[sat[i].x].y, sol[sat[i].y].y));
if (!tmpArr[sat[i].x]) tmpCnt ++;
tmpArr[sat[i].x] ++;
if (!tmpArr[sat[i].y]) tmpCnt ++;
tmpArr[sat[i].y] ++;
}
}
for (int i = 1; i <= m; i ++) {
if ((st >> (i - 1)) & 1)
tmpArr[sat[i].x] = tmpArr[sat[i].y] = 0;
}
if (mxp > mnp)
continue;
int tot = popcount (st);
Answer = (Answer + ((tot & 1) ? -1 : 1) * (dp[mnp][tmpCnt] - dp[mxp - 1][tmpCnt]) % mod + mod) % mod;
}
printf ("%lld\n", Answer);
return 0;
}
```
### [P8737 [蓝桥杯 2020 国 B] 质数行者](https://www.luogu.com.cn/problem/P8737)
正常 dp 思路实现是 $O(n^3 cnt)$,其中 $cnt$ 为质数个数,结合容斥我们可以从前两维向第三维合并,具体一点:
$$
dp_{i,j,k} = \displaystyle\sum^{n}_{i=0}\displaystyle\sum^{m}_{j=0}\displaystyle\sum^{w}_{k=0}{dp_{i - prime_t,j,k} \times dp_{i,j - prime_t,k} \times dp_{i,j,k - prime_t} \times \frac{(i + j + k)!}{i! j! k!}} \\ \Downarrow \\ dp_{i,j} = \displaystyle\sum^{n}_{i=0}\displaystyle\sum^{m}_{j=0}{dp_{i - prime_t,j - 1}} \\ g_{i + j} = \displaystyle\sum^{n}_{i=0}\displaystyle\sum^{m}_{j=0}{dp_{n,i} \times dp_{m,j} \times \frac{(i + j)!}{i!j!}} \\ tmpSum = \displaystyle\sum^{n + m}_{i=0}\displaystyle\sum^{w}_{j=0}{g_i \times dp_{w,j} \times \frac{(i + j)!}{i!j!}}
$$
答案需要容斥计算: $(1,1,1)$ 到 $(n,m,w)$ 的方案减去 $(1,1,1) \to (r_i,h_i,c_i) \to (n,m,w)$ 的方案数,其中 $i \in \{1,2\}$,加上 $(1,1,1) \to (r_1,h_1,c_1) \to (r_2,h_2,c_2) \to (n,m,w)$ 的方案数和 $(1,1,1) \to (r_2,h_2,c_2) \to (r_1,h_1,c_1) \to (n,m,w)$ 的方案数。
参考代码:
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline void read (int &x) {
int res (0), f (1);
char ch (getchar());
while (!isdigit (ch)) f = ch == '-' ? -1 : 1, ch = getchar();
while (isdigit (ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
x = res * f;
}
const int maxn (1e3 + 5), mod (1e9 + 7);
int n, m, w, r[3], c[3], h[3], dp[maxn][maxn], fac[maxn << 2], invfac[maxn << 2], prime[maxn << 2], idx, maxCube, g[maxn << 2];
bool isprime[maxn << 2];
inline int binpow (int x, int k) {
int tmpVal (1);
while (k) {
if (k & 1) tmpVal = tmpVal * x % mod;
x = x * x % mod;
k >>= 1;
}
return tmpVal;
}
inline void Getfac() {
fac[0] = invfac[0] = 1;
for (int i (1); i <= 3e3; i ++)
fac[i] = fac[i - 1] * i % mod;
invfac[3000] = binpow (fac[3000], mod - 2);
for (int i (2999); i >= 1; i --)
invfac[i] = invfac[i + 1] * (i + 1) % mod;
return;
}
inline void Getprime() {
for (int i (2); i <= 3e3; i ++) {
if (!isprime[i]) prime[++ idx] = i;
for (int j (1); j <= idx && i * prime[j] <= 3e3; j ++) {
isprime[i * prime[j]] = 1;
if (!(i % prime[j])) break;
}
}
return;
}
inline void GetDp () {
dp[1][0] = 1;
for (int i (2); i <= maxCube; i ++) {
for (int k (1); k <= i; k ++) {
for (int j (1); j <= idx; j ++) {
if (prime[j] > i) continue;
dp[i][k] = (dp[i][k] + dp[i - prime[j]][k - 1]) % mod;
}
}
}
return;
}
inline int MergeDp (int x, int y, int z, int fx, int fy, int fz) {
int dx (fx - x + 1), dy (fy - y + 1), dz (fz - z + 1);
if (dx < 0 || dy < 0 || dz < 0) return 0;
fill (g, g + dx + dy + 1, 0);
for (int i (0); i <= dx; i ++) {
for (int j (0); j <= dy; j ++)
g[i + j] = (g[i + j] + fac[i + j] * invfac[i] % mod * invfac[j] % mod * dp[dx][i] % mod * dp[dy][j] % mod) % mod;
}
int tmpSum (0);
for (int i (0); i <= dx + dy; i ++) {
for (int j (0); j <= dz; j ++)
tmpSum = (tmpSum + fac[i + j] * invfac[i] % mod * invfac[j] % mod * g[i] % mod * dp[dz][j] % mod) % mod;
}
return tmpSum;
}
signed main() {
Getfac(), Getprime();
read (n), read (m), read (w);
for (int i : {1, 2}) read (r[i]), read (c[i]), read (h[i]);
maxCube = max (n, max (m, w)), GetDp();
int Answer (MergeDp (1, 1, 1, n, m, w));
for (int i : {1, 2}) {
int tmpAns = MergeDp (1, 1, 1, r[i], c[i], h[i]) * MergeDp (r[i], c[i], h[i], n, m, w) % mod;
Answer = ((Answer - tmpAns) % mod + mod) % mod;
}
int tmpAns_A (MergeDp (1, 1, 1, r[1], c[1], h[1]) * MergeDp (r[1], c[1], h[1], r[2], c[2], h[2]) % mod * MergeDp (r[2], c[2], h[2], n, m, w) % mod);
int tmpAns_B (MergeDp (1, 1, 1, r[2], c[2], h[2]) * MergeDp (r[2], c[2], h[2], r[1], c[1], h[1]) % mod * MergeDp (r[1], c[1], h[1], n, m, w) % mod);
Answer = (((Answer + tmpAns_A) % mod + tmpAns_B) % mod) % mod;
printf ("%lld\n", Answer);
return 0;
}
```
## 习题
[P6521 [CEOI2010 day2] pin](https://www.luogu.com.cn/problem/P6521)
[P5505 [JSOI2011] 分特产](https://www.luogu.com.cn/problem/P5505)
[P4859 已经没有什么好害怕的了](https://www.luogu.com.cn/problem/P4859)
[P10986 [蓝桥杯 2023 国 Python A] 2023](https://www.luogu.com.cn/problem/P10986)