浅谈二项式反演

这部分内容摘自 OI 中的数学基础中组合数学部分，将并入之后更新的第二版内容。

OI 中的数学基础の洛谷链接。

如果某些计数问题的限制是“某些物品恰好若干个”，就可以考虑使用二项式反演。

原理

设 fnf_n 表示恰好使用 nn 个不同元素形成特定结构的方案数，gng_n 表示从这 nn 个不同元素中选出若干个元素形成特定结构的方案数。

已知 fnf_n 求 gng_n 是简单的，枚举选出多少个元素有

gn=∑i=0nCnifig_n=\sum_{i=0}^{n} C_n^i f_i

反着做却是困难的，这个过程就叫二项式反演。有公式：

fn=∑i=0nCni(−1)n−igif_n=\sum_{i=0}^{n} C_n^i (-1)^{n-i}g_i

二项式反演的作用就是把“恰好”转化为“钦定”。

:::success[证明]

组合意义上，考虑容斥原理，思考一下每个集合被重复计算几次可以感性理解。下面给出严谨的代数推导。

我们先给出一个引理

CnrCrk=CnkCn−kr−kC_n^r C_r^k=C^k_n C^{r-k}_{n-k}

组合意义和代数推导都易证。

把上述式子展开：

fn=∑i=0nCni(−1)n−i[∑j=0iCijfj]=∑i=0n∑j=0iCniCij(−1)n−ifj=∑j=0n∑i=jnCniCij(−1)n−ifj=∑j=0n[fj×∑i=jnCniCij(−1)n−i]\begin{aligned} f_n&=\sum_{i=0}^{n} C_n^i (-1)^{n-i} [\sum_{j=0}^{i} C_i^j f_j]\\ &=\sum_{i=0}^{n} \sum_{j=0}^{i} C_n^i C_i^j (-1)^{n-i} f_j \\ &= \sum_{j=0}^{n} \sum_{i=j}^{n} C_n^i C_i^j (-1)^{n-i} f_j \\ &= \sum_{j=0}^{n} [f_j \times \sum_{i=j}^{n} C_n^i C_i^j (-1)^{n-i} ] \end{aligned}

根据引理可得

fn=∑j=0n[fj×∑i=jnCnjCn−ji−j(−1)n−i]=∑j=0n[Cnjfj×∑i=jnCn−ji−j(−1)n−i]\begin{aligned} f_n&=\sum_{j=0}^{n} [f_j \times \sum_{i=j}^{n} C_n^j C_{n-j}^{i-j} (-1)^{n-i} ]\\ &=\sum_{j=0}^{n} [C_n^j f_j \times \sum_{i=j}^{n}C_{n-j}^{i-j} (-1)^{n-i} ]\\ \end{aligned}

作换元，令 k=i−jk=i-j，则 i=k+ji=k+j，即有

fn=∑j=0n[Cnjfj×∑k=0n−jCn−jk(−1)n−j−k]=∑j=0n[Cnjfj×∑k=0n−jCn−jk(−1)n−j−k1k]\begin{aligned} f_n&=\sum_{j=0}^{n} [C_n^j f_j \times \sum_{k=0}^{n-j}C_{n-j}^{k} (-1)^{n-j-k} ]\\ &=\sum_{j=0}^{n} [C_n^j f_j \times \sum_{k=0}^{n-j}C_{n-j}^{k} (-1)^{n-j-k}1^k ] \end{aligned}

根据二项式定理，当且仅当 n=jn=j 时 ∑k=0n−jCn−jk(−1)n−j−k1k\sum_{k=0}^{n-j}C_{n-j}^{k} (-1)^{n-j-k}1^k 为 11，故：

fn=fnf_n=f_n

上述操作均为等价变换，证毕。

:::

下面我们给出二项式反演的全部形式：

f(n)=∑i=0n(−1)iCnig(i)⇔g(i)=∑i=0n(−1)iCnif(i)f(n)=∑i=nmCmig(i)⇔g(n)=∑i=nm(−1)m−iCmif(i)f(n)=∑i=nmCnig(i)⇔g(n)=∑i=nm(−1)i−nCnif(i)\begin{aligned} &f(n)=\sum_{i=0}^n (-1)^iC_n^i g(i) \Leftrightarrow g(i)=\sum_{i=0}^n (-1)^i C_n^i f(i)\\ &f(n)=\sum_{i=n}^m C_m^ig(i) \Leftrightarrow g(n)=\sum_{i=n}^m (-1)^{m-i} C_m^i f(i)\\ &f(n)=\sum_{i=n}^m C_n^i g(i) \Leftrightarrow g(n)=\sum_{i=n}^m (-1)^{i-n} C_n^i f(i) \end{aligned}

例题

AT_abc423_f [ABC423F] Loud Cicada

设 gxg_x 表示钦定 xx 种蝉爆发的方案数。状压枚举集合 SS，则

gx=∑popcount⁡(S)=x⌊Ylcm⁡i∈Sai⌋g_x=\sum _{\operatorname{popcount}(S) = x} \lfloor \dfrac{Y}{\operatorname{lcm}_{i \in S} a_i} \rfloor

解释一下，对于集合 SS 中的所有元素 ii，求出 aia_i 的最小公倍数，则集合 SS 中的所有蝉爆发的充要条件就是年份为最小公倍数的倍数。在 YY 以内共有 ⌊Ylcm⁡i∈Sai⌋\lfloor \dfrac{Y}{\operatorname{lcm}_{i \in S} a_i} \rfloor 个年份。

然后做二项式反演：

fm=∑i=mnCmi(−1)igif_m=\sum_{i=m}^{n} C_m^i (-1)^{i}g_i

复杂度 O(n2n)O(n2^n)，杨辉三角 O(n2)O(n^2) 预处理组合数即可。注意 lcm⁡\operatorname{lcm} 最好开个 __int128。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define popcount __builtin_popcount
const int N = 25;
int n, m;
long long y, a[N], g[N], c[N][N];

void _main() {
	cin >> n >> m >> y;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i <= n; i++) c[i][0] = 1, c[i][i] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
	}
	for (int s = 0; s < (1 << n); s++) {
		__int128 x = 1;
		for (int i = 1; i <= n; i++) {
			if (s >> (i - 1) & 1) x = x / __gcd<__int128>(x, a[i]) * a[i];
			if (x > y) break;  // 注意这句
		} g[popcount(s)] += y / x;  
	}
	long long res = 0;
	for (int i = m; i <= n; i++) {
		if ((m - i) & 1) res -= c[i][m] * g[i];
		else res += c[i][m] * g[i];
	} cout << res;
}

:::

P10596 BZOJ2839 集合计数

看到不好求的“恰好”，考虑二项式反演。设 fif_i 表示交集大小恰好为 ii 的方案数，gig_i 表示钦定 ii 个元素属于交集的方案数。

那么对于 gig_i，先从 nn 个元素中选出 ii 个，方案数 CniC_n^i。剩下 n−in-i 个元素可选可不选，就是求大小为 2n−i2^{n-i} 的集合的非空子集数，答案为 22n−i−12^{2^{n-i}}-1，乘法原理：

gi=Cni(22n−i−1)g_i=C_n^i (2^{2^{n-i}}-1)

上二项式反演：

fk=∑i=kn(−1)i−kCikgif_k=\sum_{i=k}^{n}(-1)^{i-k} C_i^k g_i

复杂度 O(nlog⁡n)O(n \log n)。注意求 gig_i 要用欧拉定理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 1e6 + 5;
mint fac[N], ifac[N], g[N];
mint C(int n, int m) {
	return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];
}
int n, k;
void _main() {
	cin >> n >> k;
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i];
	for (int i = 0; i <= n; i++) g[i] = C(n, i) * (mint(2).pow(mod32<1000000006>(2).pow(n - i).val) - 1);
	mint res = 0;
	for (int i = k; i <= n; i++) {
		if ((i - k) & 1) res -= C(i, k) * g[i];
		else res += C(i, k) * g[i];
	} cout << res;
}

P4859 已经没有什么好害怕的了

形式化题意：给出长为 nn 的序列 a,ba,b，将其两两配对使得 ai>bia_i>b_i 的数目减去 ai<bia_i<b_i 的数目恰为 kk，求方案数。

设 ai>bia_i>b_i 的数量为 mm，则 m−(n−m)=km-(n-m)=k，解得 m=n+k2m=\dfrac{n+k}{2}。若 2∤(n+k)2 \nmid (n+k)，直接判定无解。此时问题变成 ai>bia_i>b_i 的数目恰好为 mm。考虑使用二项式反演化恰好为钦定。设 gig_i 为 ai>bia_i>b_i 的组数不小于 ii 的方案数，根据二项式反演所求为

∑i=mn(−1)i−mCikgi\sum_{i=m}^{n} (-1)^{i-m} C_{i}^k g_i

现在的问题就是求 gig_i，这玩意很 DP，所以设 dpi,jdp_{i,j} 表示前 ii 个数中选出 jj 组 ai>bia_i>b_i 的方案数。DP 题套路对 a,ba,b 排序，然后可以推出转移方程

dpi,j=dpi−1,j+(lasti−j+1)dpi−1,j−1dp_{i,j}=dp_{i-1,j}+(last_i-j+1)dp_{i-1,j-1}

从插入角度考虑 (ai,bi)(a_i,b_i) 的贡献，一种情况是不作为新的 ai>bia_i>b_i，还有一种就是考虑有多少个取代位置。设 lastilast_i 表示 bb 序列中第一个小于 aia_i 的数的下标，则插入位置就有 lasti−j+1last_i-j+1 个，加法原理合并答案。

于是我们 O(n2)O(n^2) 求出 dpi,jdp_{i,j}。考察 gig_i 的定义可得

gi=dpn,i×(n−i)!g_i=dp_{n,i}\times (n-i)!

就是在有序的 dp 基础上考虑剩下 n−in-i 个全排列。

二项式反演中组合数可以逆元法来求，总复杂度 O(n2)O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const int N = 2005;
int n, m, k, a[N], b[N], last[N];
mint fac[N], ifac[N], dp[N][N], g[N];
mint C(int n, int m) {
	if (n < m) return 0;
	return fac[n] * ifac[m] * ifac[n - m]; 
}

void _main() {
	cin >> n >> k;
	if ((n + k) & 1) return cout << 0, void();
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i];
	
	m = (n + k) / 2;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i++) last[i] = lower_bound(b + 1, b + n + 1, a[i]) - b - 1;
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = dp[i - 1][0];
		for (int j = 1; j <= i; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * max(0, last[i] - j + 1);
		}
	}
	for (int i = 0; i <= n; i++) g[i] = dp[n][i] * fac[n - i];
	mint res = 0;
	for (int i = m; i <= n; i++) {
		if ((i - m) & 1) res -= C(i, m) * g[i];
		else res += C(i, m) * g[i];
	} cout << res;
}

P6478 [NOI Online #2 提高组] 游戏

“恰好 kk 次非平局”很难处理，不妨转为“钦定 kk 次非平局”。设恰好 kk 次非平局的方案数为 g(k)g(k)，钦定 kk 次非平局的方案数为 f(k)f(k)，显然有 f(n)=∑i=nmCing(i)f(n)=\sum_{i=n}^m C_i^n g(i)，根据二项式反演：

g(n)=∑i=nm(−1)i−nCinf(i)g(n)=\sum_{i=n}^m (-1)^{i-n} C_i^n f(i)

考虑求 f(i)f(i) 即可。考虑树形 DP，设 dpu,idp_{u,i} 表示在以 uu 为根的子树中钦定 ii 个点且必须有胜负的方案数。

考虑对于儿子 vv 枚举在 vv 中选择 jj 个点，有转移：

dpu,i=∑(u,v)∑j=0idpv,jdpu,i−jdp_{u,i}=\sum_{(u,v)} \sum_{j =0}^i dp_{v,j}dp_{u,i-j}

还可以选择一个点与 uu 配对，于是：

dpu,i←dpu,i+dpu,i−1+cntu,x⊕1dp_{u,i} \gets dp_{u,i}+dp_{u,i-1}+cnt_{u,x \oplus 1}

其中 xx 为点 uu 属于哪位玩家，cntu,0/1cnt_{u,0/1} 表示以 uu 为根的子树中有多少个属于 0/10/1 玩家。

这是一个树形背包，且应该跑 01 背包。根据树形背包的复杂度证明，复杂度是严格 O(n2)O(n^2) 的。

这样有 g(i)=dp1,i×(m−i)!g(i)=dp_{1,i}\times (m-i)!。求出来以后套进二项式反演即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
const int N = 5005;
int n, m, u, v, belong[N];
char c;
int tot = 0, head[N];
struct Edge {
	int next, to;
} edge[N << 1];
inline void add_edge(int u, int v) {
	edge[++tot].next = head[u], edge[tot].to = v, head[u] = tot;
}
mint f[N], g[N], fac[N], ifac[N];
mint C(int n, int m) {return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m];}

int sz[N], cnt[2][N];
mint dp[N][N];
void dfs(int u, int fa) {
	sz[u] = 1, cnt[belong[u]][u] = 1, dp[u][0] = 1;
	for (int j = head[u]; j != 0; j = edge[j].next) {
		int v = edge[j].to;
		if (v == fa) continue;
		dfs(v, u);
		vector<mint> f(min(sz[u] + sz[v], m), 0);
		for (int j = 0; j <= min(sz[u], m); j++) {
			for (int k = 0; k <= min(sz[v], m - j); k++) {
				f[j + k] += dp[u][j] * dp[v][k];
			}
		}
		sz[u] += sz[v], cnt[0][u] += cnt[0][v], cnt[1][u] += cnt[1][v];
		copy(f.begin(), f.end(), dp[u]);
	}
	for (int i = cnt[belong[u] ^ 1][u]; i >= 0; i--) {
		dp[u][i + 1] += dp[u][i] * (cnt[belong[u] ^ 1][u] - i);
	}
}

void _main() {
	fac[0] = ifac[0] = 1;
	for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i];
	cin >> n, m = n / 2;
	for (int i = 1; i <= n; i++) cin >> c, belong[i] = c ^ 48;
	for (int i = 1; i < n; i++) {
		cin >> u >> v;
		add_edge(u, v), add_edge(v, u);
	}
	dfs(1, -1);
	for (int i = 0; i <= m; i++) g[i] = dp[1][i] * fac[m - i];
	for (int i = 0; i <= m; i++) {
		for (int j = i; j <= m; j++) {
			if ((j - i) & 1) f[i] -= C(j, i) * g[j];
			else f[i] += C(j, i) * g[j];
		}
		cout << f[i] << '\n';
	}
}

总结

二项式反演的主要作用就是把“恰好”变成“至少 / 至多”，也就是上文所述的“钦定”。

一般二项式反演适用于“恰好”很难做，而“钦定”比较好做的情况。对于“钦定”这一部分，往往要结合计数 DP 的方法求解。