【组合数学】二项式相关与容斥

· · 算法·理论

二项式定理

(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)