【学习笔记】二项式反演 & 子集反演

Posted on Edited on

概念

二项式反演为一种反演形式, 通常用于 指定某若干个 求 恰好若干个 的问题.

二项式反演虽然形式上和多步容斥类似, 但并不等价, 只是形式上都叫多步容斥.

转载

二项式反演

形式 $1$

将多步容斥公式用补集的形式表示.

记 $f(n)$ 表示 $n$ 个补集的交集大小, $g(n)$ 表示 $n$ 个原集的大小, 则他们可以分别写成:

这两个公式是等价关系, 是相互推导的关系,所以:

形式 $2$

证明 $1$

在形式 $1$ 中, 令 $h(n) = (-1)^n g(n)$ , 则:

证明 $2$

将右式代入左式子:

当 $n-j \not= 0$ 时, 显然 $(1-1)^{n-j} = 0$ .

当 $n-j = 0$ 时, 不能直接计算, 需要用组合数求解, 此时 $\binom{n-j}{k}(-1)^k = 1$ .

故 $f(n) = \binom{n}{n}f(n) = f(n)$ .

左右恒等, 证毕.

由于证明 $2$ 并没有用到 $i$ 从 $0$ 开始这一性质, 所以:

组合意义

记 $f(n)$ 表示 “钦定(最多)选 $n$ 个”, $g(n)$ 表示 “恰好选 $n$ 个”.

形式 $3$

最为常用.

证明

左右恒等, 证毕.

组合意义记 $f(n)$ 表示 “钦定(至少)选 $n$ 个”, $g(n)$ 表示 “恰好选 $n$ 个”

记 $f(n)$ 表示 “钦定(至少)选 $n$ 个”, $g(n)$ 表示 “恰好选 $n$ 个”, 则对于任意的 $i \geqslant n$ , $g(i)$ 在 $f(n)$ 中被计算了 $\binom{i}{n}$ 次, 故 $f(n) = \sum\limits_{i=n}^{m}{\binom{i}{n} g(n)}$ , 其中 $m$ 是数目上界.

不同的题目对于钦定的定义不一定相同, 要对于具体问题具体分析.

例题

P5505 [JSOI2011]分特产

简要题意

有 $n$ 个人和 $m$ 种物品, 第 $i$ 种物品有 $a_i$ 个, 同种物品之间没有区别. 分物品, 求每个人至少有一个物品的方案数.

题解

对于求每个人至少有一个不是很好办, 转变成求恰好 $0$ 个人没有分到物品的方案.

设 $f_i$ 表示钦定(至少) $i$ 个人没有分到物品的方案, $g_i$ 表示恰好有 $i$ 个人没有分到物品的方案.

考虑怎么计算 $f_k$ , 对于第 $i$ 种物品, 相当于把 $a_i$ 个物品分给 $n-t$ 个人, 方案数为 $\binom{a_i+n-t-1}{a_i}$ .

于是 $f_t = \binom{n}{t} \prod\limits_{i=1}^{m}{\binom{a_i+n-t-1}{a_i}}$ .

二项式反演后代入 $f_i$ .

最终的答案 $g_0 = \sum\limits_{i=0}^{n}{(-1)^i \binom{n}{i} \prod\limits_{j=1}^{m}{\binom{a_j+n-i-1}{a_j}}}$ .

代码
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
55
56
57
58
59
60
61
62
63
/************************************************
*Author        :  demonlover
*Created Time  :  2021.11.15.20:26
*Problem       :  luogu5505
************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << endl
template <typename T>
inline bool read(T &x) {
	int f = 1,c = getchar();x = 0;
	while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
	while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
	return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
	return read(x) && read(args...);
}

namespace run {
	const int maxn = 1e3+10;
	const int mod = 1e9+7;
	int c[maxn<<1][maxn<<1],a[maxn];
	int n,m,ans;
	inline void init() {
		c[0][0] = 1;
		for (int i = 1;i <= 2000;++i) {
			c[i][0] = 1;
			for (int j = 1;j <= i;++j)
				c[i][j] = (c[i-1][j]+c[i-1][j-1])%mod;
		}
		return;
	}
	inline int main() {
		init();
		read(n,m);
		for (int i = 1;i <= m;++i)read(a[i]);
		for (int i = 0;i <= n;++i) {
			int tmp = c[n][i];
			for (int j = 1;j <= m;++j)
				tmp = 1ll*tmp*c[a[j]+n-i-1][a[j]]%mod;
			if (!(i&1))ans = (ans+tmp)%mod;
			else ans = (ans-tmp+mod)%mod;
		}
		printf("%d\n",ans);
		cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
		return 0;
	}
}

#define demonlover
int main() {
#ifdef demonlover
	freopen("luogu5505.in","r",stdin);
	freopen("luogu5505.out","w",stdout);
#endif
	return run :: main();
}

子集反演

基本形式

证明

其中

有

扩展形式

证明

再取补集即可.