【OI】容斥原理-二项式反演 – GWBailangの卷心菜园

二项式定理

二项式定理确实跟二项式反演有点关系，都是二项式，所以这里要提一句，证明都很显然就不说了。

定理如下：

(a+b)^n=\sum\limits_{i=0}^{n}\binom{n}{i}a^{i}b^{n-i}

带入 $a=-1,b=1$ 得：

\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^{i}=(1-1)^n=[n=0]

广义二项式定理：

\left (\sum\limits_{i=1}^{m}a_i\right)^n=\sum\limits_{x_1+x_2+\dots+x_m=n}\binom{n}{x_1,x_2,\dots,x_m}\prod_{i=1}^{m}a_i^{x_i}

二项式反演如下：

g(n)=\sum\limits_{i=0}^{n}\binom{n}{i}f(i)\Longleftrightarrow f(n)=\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^{n-i}g(i)

证明如下：

将第一个式子子带入 $\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^{n-i}g(i)$ 得：

\sum\limits_{i=0}^{n}\binom{n}{i}(-1)^{n-i} \left [\sum\limits_{j=0}^{i}\binom{i}{j}f(i)\right]

根据组合数的性质 $\binom{n}{i}\binom{i}{j}=\binom{n}{j}\binom{n-j}{i-j}$，交换求和顺序得：

\sum\limits_{j=0}^{n}f(j)\binom{n}{j}\sum\limits_{i=j}^{n}(-1)^{i-j}\binom{n-j}{i-j}

令 $i’=i-j$：

\sum\limits_{j=0}^{i}f(j)\binom{n}{j}\sum\limits_{i’=0}^{n-j}(-1)^{i’}\binom{n-j}{i’}

根据上述二项式定理得：

\sum\limits_{j=0}^{i}f(j)\binom{n}{j}[n-j=0]

只有当 $j=n$ 时，$[n-j=0]=1$，其余均为 $0$，对和没有贡献。所以原式等于：

f(n)\binom{n}{n}=f(n)

全矣！

二项式反演还有一种“后缀和”的形式：

g(n)=\sum\limits_{i=n}^{N}\binom{i}{n}f(i)\Longleftrightarrow f(n)=\sum\limits_{i=n}^{N}\binom{i}{n}(-1)^{i-n}g(i)

证明和上面的差不多，这里不写了。

有一个 $n$ 个元素的集合，需要在其 $2^n$ 个子集中取出至少一个集合，使它们的交集元素个数为 $k$。求方案数，对 $P=10^9+7$ 取模。$n,k\le 10^6$。

令 $f(x)$ 表示钦定 $x$ 个元素在交集中，其余元素不作限制的方案数，令 $g(x)$ 表示交集大小恰好为 $x$ 的方案数。那么显然答案就是 $g(k)$。

【词典·A.艾硕德】钦定

“钦定”到底是什么意思？

简单来说，“钦定” = 强制要求 + 其余随意（不作限制）。

恰好 $x$ 个（$g(x)$）：我要求交集里的元素不多不少就是这 $x$ 个。外面的 $N-x$ 个元素，绝对不能出现在交集里。这种限制非常严格，直接去算是很难求的。
钦定 $x$ 个（$f(x)$）：我强制选出 $x$ 个元素，保证它们一定在交集里。至于剩下的 $N-x$ 个元素，它们到底在不在交集里？我根本不关心，随它们的便。它们可能在，也可能不在。

这就意味着，在 $f(x)$ 的统计中，实际的交集大小可能等于 $x$，也可能大于 $x$。很多人习惯把“钦定”理解为“至少”，但这在计数时是不严谨的，因为“钦定”带有多重计算（重复统计）的特性。

考虑如何表示 $f(x)$：由于要求集合的并包含 $x$ 个元素，剩下 $n-x$ 个元素随意，所以一共有 $2^{n-x}$ 个集合可以选择。又由于不能一个都不选，所以选集合的方案数就是 $2^{2^{n-x}}-1$。再乘上 $n$ 个元素中选 $x$ 个元素的方案数，得到：

f(x)=\binom{n}{x}\left(2^{2^{n-x}}-1\right)

再根据 $g(x)$ 的定义得到：

f(x)=\sum_{y=x}^{n} \binom{y}{x} g(y)

即对于任意的 $y\ge x$，让选出的 $x$ 个元素属于选出的 $y$ 个元素，也就是 $y$ 个元素中选出 $x$ 个元素。这样 $g(y)$ 就对 $f(x)$ 有系数为 $\binom{y}{x}$ 的贡献。

这显然就是上述的二项式反演：

g(k)=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}f(i)

带入 $f(i)$ 得：

g(k)=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}\binom{n}{i}\left(2^{2^{n-i}}-1\right)

根据费马小定理 $a^{P-1}\equiv 1\pmod P$，$2^{2^{n-i}}=2^{2^{n-i}\bmod(P-1)}$，然后用快速幂求即可。

由于 $n,k\le 10^6$，这里的每一项也都可以直接求出或线性递推，所以总复杂度 $O(n\log P)$。