<span>总结「二项式反演」</span>

转载注明来源：https://www.cnblogs.com/syc233/p/13455373.html

二项式反演 ~ Inversion of the Binomial

前置知识容斥原理

\[\big | \bigcup_{i=1}^n A_i \big |=\sum_i \big|A_i \big|- \sum_{i<j}\big|A_i \cap A_j\big|+\sum_{i<j<k}\big|A_i\cap A_j \cap A_k\big|- \cdots+(-1)^{n-1} \sum_{a_i<a_{i+1}} \big|\bigcap_{i-1}^n A_{a_i}\big| \]

二项式反演

记 \(\complement A\) 为 \(A\) 的补集。设全集为 \(S\) ，则有：

\[A \cup B=S-\complement A \cap \complement B \]

我们可以对容斥的式子进行变形：

\[\big|\bigcap_{i=1}^n \complement A_i\big|=\big|S\big|-\sum_i \big|A_i \big|+ \sum_{i<j}\big|A_i \cap A_j\big|-\sum_{i<j<k}\big|A_i\cap A_j \cap A_k\big|+ \cdots+(-1)^n \sum_{a_i<a_{i+1}} \big|\bigcap_{i-1}^n A_{a_i}\big| \tag{1} \]

将容斥的式子中 \(A_i\) 替换为 \(\complement A_i\) ，再进行相同的变形：

\[\big|\bigcap_{i=1}^n A_i\big|=\big|S\big|-\sum_i \big|\complement A_i \big|+ \sum_{i<j}\big|\complement A_i \cap \complement A_j\big|-\sum_{i<j<k}\big|\complement A_i\cap \complement A_j \cap \complement A_k\big|+ \cdots+(-1)^n \sum_{a_i<a_{i+1}} \big|\bigcap_{i-1}^n \complement A_{a_i}\big| \tag{2} \]

考虑一种特殊情况：对于任意一个集族 \(\mathcal{U}=\{A_1,A_2,A_3,\cdots,A_n\}\) ，其中任意 \(i\) 个集合的交集都为 \(g(i)\) ，则：

\[g(n)=\big|\bigcap_{a_i<a_{i+1}}^n A_{a_i}\big| \]

并且定义 \(g(0)=|S|\) 。

类似地，令

\[f(n)=\big|\bigcap_{a_i<a_{i+1}}^n \complement A_{a_i}\big| \]

将 \(f,g\) 代入 \((1),(2)\) 两式中得：

\[f(n)=\sum_{i=0}^n (-1)^i {n \choose i}g(i) \iff g(n)=\sum_{i=0}^n (-1)^i{n \choose i}f(i) \]

二项式反演的不同形式

形式一

\[f(n)=\sum_{i=0}^n (-1)^i {n \choose i}g(i) \iff g(n)=\sum_{i=0}^n (-1)^i{n \choose i}f(i) \]

就是上面那个式子。

形式二

\[f(n)=\sum_{i=0}^n {n \choose i} g(i) \iff g(n)=\sum_{i=0}^n(-1)^{n-i}{n \choose i}f(i) \]

这个形式比较好推。不难发现其中 \(g(i)\) 即为形式一中的 \((-1)^ig(i)\) ，代入即可。

形式三

\[f(n)=\sum_{i=n}^m {i \choose n}g(i) \iff g(n)=\sum_{i=n}^m(-1)^{i-n} {i \choose n} f(i) \]

将右式代入左式可得证。

BZOJ2839 集合计数

题面

一个有 \(N\) 个元素的集合有 \(2^N\) 个不同的子集。选出若干个子集（至少一个），使得其交集的元素个数恰好为 \(K\)，求有多少种取法。

题解

设 \(f(k)\) 表示选定 \(k\) 个交集元素的方案数，则有：

\[f(k)={n \choose k}(2^{2^{n-k}}-1) \]

式中 \({n \choose k}\) 表示选定 \(k\) 个元素的方案数。选定 \(k\) 个元素后，还剩下 \(n-k\) 个元素，即有 \(2^{n-k}\) 个集合可以选择，即有 \(2^{2^{n-k}}-1\) 种选择集合的方案（至少选一个集合，除去空集）。

设 \(g(i)\) 表示交集元素恰好为 \(i\) 个的方案数。因为选定 \(k\) 个交集元素后，实际的交集元素个数只会大于等于 \(k\) ，则有：

\[f(k)=\sum_{i=k}^n {i \choose k} g(i) \]

这就是一个典型的二项式反演的形式三，可以得到：

\[g(k)=\sum_{i=k}^n (-1)^{i-k} {i \choose k} f(i) =\sum_{i=k}^n (-1)^{i-k} {i \choose k} {n \choose i}(2^{2^{n-i}}-1) \]

于是就可以 \(O(n)\) 求 \(g(k)\) 了。

\(\text{Code:}\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 1000005
#define R register
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
const lxl mod=1e9+7;

inline lxl read()
{
	lxl x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}

lxl N,K;
lxl inv[maxn],invf[maxn],fac[maxn];

inline void init()// 预处理一下逆元
{
	inv[1]=invf[1]=invf[0]=fac[1]=fac[0]=1;
	for(lxl i=2;i<=N;++i)
	{
		inv[i]=(-(mod/i)*inv[mod%i]%mod+mod)%mod;
		invf[i]=invf[i-1]*inv[i]%mod;
		fac[i]=fac[i-1]*i%mod;
	}
}

inline lxl C(int n,int m)
{
	return fac[n]*invf[n-m]%mod*invf[m]%mod;
}

int main()
{
	// freopen("P2839.in","r",stdin);
	N=read(),K=read();
	init();
	lxl ans=0,tmp=1,type=((N-K)&1)?-1:1;
	for(int i=N;i>=K;--i)
	{
		ans=(ans+type*C(i,K)%mod*C(N,i)%mod*tmp%mod+mod)%mod;
		tmp=tmp*(tmp+2)%mod;
		type=-type;
	}
	printf("%lld\n",ans);
	return 0;
}

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

~~按住老虚~~

题面

给定两个长为 \(N\) 的数列 \(A,B\) ，将 \(A\) 与 \(B\) 中的数两两配对，求满足 \(A_i>B_j\) 的数对数比 \(A_i<B_j\) 的数对数恰好多 \(k\) 的配对方案数。

题解

设 \(A_i>B_j\) 的数对数为 \(m\) ，则 \(A_i<B_j\) 的数对数为 \(n-m\) ，由 \(m-(n-m)=k\) 解出 \(A_i>B_j\) 的数对数 \(m=\frac{n+k}{2}\)。

首先 \(n+k \equiv 1 \ ({\rm{mod}} \ 2)\) 时无解，特判掉这种情况。

将 \(A,B\) 排序。设 \(dp_{i,j}\) 表示考虑了数列 \(A\) 中的前 \(i\) 个数，组成了至少 \(j\) 个满足 \(A_i>B_j\) 的数对的方案数（这里并没有考虑其他数的不同组合方案）。则转移：

一种情况是 \(A_i\) 对答案不做出贡献，那么 \(dp_{i,j}\) 直接从 \(dp_{i-1,j}\) 转移过来。
另一种情况是 \(A_i\) 与 \(B\) 中一个数对答案产生 \(1\) 的贡献。设 \(B\) 中比 \(A_i\) 小的数有 \(cnt\) 个，其中有 \(j-1\) 个数与 \(A_i\) 之前的数配对，则 \(A_i\) 有 \(cnt-(j-1)\) 种配对方案，那么 \(dp_{i,j}\) 从 \(dp_{i-1,j-1} \times (cnt-j+1)\) 转移而来

综上有：

\[dp_{i,j}=dp_{i-1,j}+(cnt-j+1) \times dp_{i-1,j-1} \]

设 \(f(m)\) 表示至少有 \(m\) 个 \(A_i>B_j\) 的数对的方案数，\(g(m)\) 表示恰好有 \(m\) 个 \(A_i>B_j\) 的数对的方案数。则有：

\[f(m)=\sum_{i=m}^n {i \choose m} g(i) \]

因为除了指定的 \(m\) 个满足 \(A_i>B_j\) 的数对，\(A\) 中还有 \(n-m\) 个数可以与 \(B\) 中 \(n-m\) 个数自由组合，则有：

\[f(m)=(n-m)!dp_{n,m} \]

由二项式反演的形式三可得：

\[g(m)=\sum_{i=m}^n (-1)^{i-m} {i \choose m} f(i) =\sum_{i=m}^n (-1)^{i-m} {i \choose m}(n-i)!dp_{n,i} \]

直接求这个和式即可。

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 2005
#define R register
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
const lxl mod=1e9+9;

inline lxl read()
{
	lxl x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}

int n,k,m;
lxl a[maxn],b[maxn],f[maxn][maxn];
lxl inv[maxn],invf[maxn],fac[maxn];

inline void init()
{
	inv[1]=inv[0]=invf[0]=invf[1]=fac[0]=fac[1]=1;
	for(lxl i=2;i<=n;++i)
	{
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		invf[i]=invf[i-1]*inv[i]%mod;
		fac[i]=fac[i-1]*i%mod;
	}
}

inline lxl C(int n,int m)
{
	return fac[n]*invf[n-m]%mod*invf[m]%mod;
}

int main()
{
	// freopen("P4859.in","r",stdin);
	n=read(),k=read();
	if((n+k)&1) {puts("0");return 0;}
	init();
	m=(n+k)>>1;
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		b[i]=read();
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	f[0][0]=1;
	for(int i=1;i<=n;++i)
	{
		int cnt=lower_bound(b+1,b+n+1,a[i])-b-1;
		f[i][0]=1;
		for(int j=1;j<=n;++j)
			f[i][j]=(f[i-1][j]+f[i-1][j-1]*(cnt-j+1)%mod)%mod;
	}
	lxl ans=0;
	for(int i=m,type=1;i<=n;++i,type=-type)
		ans=(ans+type*C(i,m)%mod*fac[n-i]%mod*f[n][i]%mod+mod)%mod;
	printf("%lld\n",ans);
	return 0;
}

总结「二项式反演」