发布于 ,更新于 

二项式反演

定义

直接给出式子:

\[ g_i=\sum_{k\geqslant i}\binom ki f_k \rightarrow f_i=\sum_{k\geqslant i}\binom ki (-1)^{k-i}g_k \]

看起来不知道咋用?待会再说,我们先证明。

证明

前置知识

组合数学常用记号

二项式定理

正文

已知:\(g_i=\sum_{k\geqslant i}\binom ki f_k\)
求证:\(f_i=\sum_{k\geqslant i}\binom ki (-1)^{k-i}g_k\)

把求证右边那个式子单独拿出来,想办法把它导成 \(f_i\)

\[ \begin{aligned} &\sum_{k\geqslant i}\binom ki (-1)^{k-i}g_k \newline =&\sum_{k\geqslant i}\binom ki (-1)^{k-i} \sum_{j\geqslant k}\binom jk f_j \end{aligned} \]

把第二个求和号以及 \(f_j\) 挪动一下,感性理解一下,发现最后每一项出现的次数还是不变的,所以正确。

\[ \begin{aligned} &\sum_{k\geqslant i}\binom ki (-1)^{k-i} \sum_{j\geqslant k}\binom jk f_j \newline =&\sum_{j\geqslant i}f_j \sum_{j\geqslant k \geqslant i}\binom jk \binom ki (-1)^{k-i} \newline =&\sum_{j\geqslant i}f_j \sum_{j\geqslant k \geqslant i}\frac{j!k!}{k!(j-k)!i!(k-i)!} (-1)^{k-i} \newline =&\sum_{j\geqslant i}f_j\frac{j!}{i!}\sum_{j\geqslant k \geqslant i}\frac 1{(j-k)!(k-i)!} (-1)^{k-i} \end{aligned} \]

展开之后不知道怎么往下算了,想办法把那个大分式化成点什么,比如二项式(组合数)。

上下同乘 \((j-i)!\),然后 \((j-k)=[(j-i)-(k-i)]\),然后就可以轻松化成组合数形式继续往下导公式了。

\[ \begin{aligned} &\sum_{j\geqslant i}f_j\frac{j!}{i!} \sum_{j\geqslant k \geqslant i}\frac 1{(j-k)!(k-i)!} (-1)^{k-i} \newline =&\sum_{j\geqslant i}f_j\frac{j!}{i!} \sum_{j\geqslant k \geqslant i}\frac {(j-i)!}{[(j-i)-(k-i)]!(k-i)!(j-i)!} (-1)^{k-i} \newline =&\sum_{j\geqslant i}f_j\frac{j!}{i!} \sum_{j\geqslant k \geqslant i}\frac {\binom{j-i}{k-i}}{(j-i)!} (-1)^{k-i} \newline \end{aligned} \]

换个形式

\[ \sum_{j\geqslant i}f_j\frac{j!}{i!} \cdot \frac{\sum_{j\geqslant k \geqslant i } \binom{j-i}{k-i} (-1)^{k-i}}{(j-i)!} \]

大分式上面的分母可以用 二项式定理 处理掉。想不出来可以直接看下面式子。

\[ \begin{aligned} &\sum_{j\geqslant i}f_j\frac{j!}{i!} \cdot \frac{\sum_{j\geqslant k \geqslant i } \binom{j-i}{k-i} (-1)^{k-i}}{(j-i)!} \newline =&\sum_{j\geqslant i}f_j\frac{j!}{i!} \cdot \frac{(1-1)^{j-i}}{(j-i)!} \end{aligned} \]

右下方的分母和左侧分数扔一起是一个非常典型的组合数。

\[ \begin{aligned} &\sum_{j\geqslant i}f_j\frac{j!}{i!} \cdot \frac{(1-1)^{j-i}}{(j-i)!} \newline =&\sum_{j\geqslant i}f_j\binom ji 0^{j-i} \end{aligned} \]

注意,在组合数学中,\(0^0=1\)
于是很容易地发现,求和号右边的式子值非零,当且仅当 \(i=j\)

于是就出来了:

\[ \begin{aligned} &\sum_{j\geqslant i}f_j\binom ji 0^{j-i}\newline =&f_i\binom ii 0^0 \newline =&f_i \end{aligned} \]

证毕。

例题

分特产

题目链接

题意

\(m\) 种特产,\(n\) 个人,每种特产 \(s_i\) 个。

人有标号,两个特产相同当且仅当其种类相同。

求让每个人都拿到至少一份特产的分配方案总数,答案对 \(10^9+7\) 取模。

题解

首先,记住开头给你的式子。

然后把下面的东西看一遍,这应该是二项式反演的基本套路。

大体上设两个东西,\(g_i\)\(f_i\)。这里设 \(g_i\)钦定 \(i\) 个人不满足要求(即没有特产),其他人随意分配(可能也没有)的方案数,然后 \(f_i\)恰好 \(i\) 个人没有特产,其他人都有特产的方案总数。

然后模仿条件式,用 \(f_i\) 表示 \(g_i\)

容易发现:

  1. 对于 \(g_i\),每一个 \(f_j,j\in [i,n]\) 都一定被包含在里面。
  2. 对于每一个包含在里面的 \(f_j\),被钦定的集合会不同,一共有 \(\binom ji\) 个,所以每个 \(f_j\) 被算了 \(\binom ji\) 次。

综上,\(g_i = \sum_{j=i}^n \binom ji f_j\)

二项式反演的常见入手点就是设 \(g,f\)。其中 \(g_i\) 表示钦定集合中 \(i\) 个元素满足/不满足要求,其他不管;\(f_i\) 表示集合中恰好 \(i\) 个元素满足/不满足要求(是否满足与 \(g\) 一致)。在此之后用 \(f_i\) 表示 \(g_i\),二项式反演之后问题就变化成了求 \(g\)

然后大力二项式反演,套一下式子就能得出来:

\[ f_i = \sum_{j=i}^n \binom ji g_j (-1)^{j-i} \]

答案就是恰好没有不合法元素的方案总数,于是:

\[ \begin{aligned} ans &= f_0 \newline &= \sum_{j=0}^n \binom j0 g_j (-1)^{j-0} \newline &= \sum_{j=0}^n g_j (-1)^j \end{aligned} \]

问题被转化成了求 \(g\)

假设目前正在求 \(g_i\),显然只需要有 \(n-i\) 个人需要考虑。由于剩下 \(i-1\) 是钦定不合法的,我们不用考虑;但是非常魔法的事情来了:由于这 \(n-i\) 个人是随便排列的,我们只需要把特产随意分发就行。

怎么个随意分发法?对于每一种特产 \(x\),可以转化为:有 \(s_x\) 个无标号小球,装进 \(n-i\) 个有标号盒子里的方案数。直接插板法解决就好啦!显然有 \(s_x-1\) 个空,除此以外,盒子可以为空,所以就是 \(s_x-1\)\(n-i\) 个空,插 \(n-i-1\) 个板的方案数,即 \(\binom{s_x-1+n-i}{n-i-1}\)

每一种特产的分配方案数互不影响,所以乘起来;同时 \(n\) 个人里面选出来 \(i\) 个钦定不合法,再乘一个 \(\binom ni\),即:

\[ g_i = \binom ni \prod_{j=1}^m \binom{s_x-1+n-i}{n-i-1} \]

然后代入上面计算答案的式子算就完了。

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>

using std::cin;
using std::cout;

namespace tkgs {
using i32 = int;
using i64 = long long;
const i64 mod = 1e9 + 7;

#define N 1005
#define NUM 2005
namespace mat {
i64 x, y, tmp;
void exgcd(const i64& a, const i64& b) {
if (!b) {
x = 1, y = 0;
} else {
exgcd(b, a % b);
tmp = x;
x = y;
y = tmp - a / b * y;
}
}

i64 inv(const i64& a, const i64& b) {
exgcd(a, b);
return x;
}

i64 fact[NUM], ifact[NUM];

void init() {
const i32 n = 2000;
fact[0] = ifact[0] = 1;
for (i32 i = 1; i <= n; ++i)
fact[i] = fact[i - 1] * i % mod;
ifact[n] = inv(fact[n], mod);
for (i32 i = n - 1; i; --i)
ifact[i] = ifact[i + 1] * (i + 1) % mod;
}

i64 getC(i32 a, i32 b) {
if (a < b)
return 0;
else
return fact[a] * ifact[b] % mod * ifact[a - b] % mod;
}
} // namespace mat 实现了初始化阶乘与阶乘逆元,求组合数

i32 s[N], n, m;

i64 g(i64 i) {
i64 res = 1;
for (i32 j = 1; j <= m; ++j)
res = res * mat::getC(s[j] + n - i - 1, n - i - 1) % mod;
res = res * mat::getC(n, i) % mod;
return res;
}

void main() {
cin >> n >> m;
for (i32 i = 1; i <= m; ++i)
cin >> s[i];
mat::init();
i64 ans = 0;
for (i32 j = 0; j < n; ++j)
(ans += g(j) * ((j & 1) ? -1 : 1)) %= mod;
cout << (ans % mod + mod) % mod;
}
} // namespace tkgs

int main() {
tkgs::main();
return 0;
}

ABC309G