转载注明来源：https://www.cnblogs.com/syc233/p/13455373.html
二项式反演 ~ Inversion of the Binomial
前置知识 容斥原理
众所周知：
二项式反演
记 (complement A) 为 (A) 的补集。设全集为 (S) ，则有：
我们可以对容斥的式子进行变形：
将容斥的式子中 (A_i) 替换为 (complement A_i) ，再进行相同的变形：
考虑一种特殊情况：对于任意一个集族 (mathcal{U}={A_1,A_2,A_3,cdots,A_n}) ，其中任意 (i) 个集合的交集都为 (g(i)) ，则：
并且定义 (g(0)=|S|) 。
类似地，令
将 (f,g) 代入 ((1),(2)) 两式中得：
二项式反演的不同形式
形式一
就是上面那个式子。
形式二
这个形式比较好推。不难发现其中 (g(i)) 即为形式一中的 ((-1)^ig(i)) ，代入即可。
形式三
将右式代入左式可得证。
BZOJ2839 集合计数
题面
一个有 (N) 个元素的集合有 (2^N) 个不同的子集。选出若干个子集（至少一个），使得其交集的元素个数恰好为 (K)，求有多少种取法。
题解
设 (f(k)) 表示选定 (k) 个交集元素的方案数，则有：
式中 ({n choose k}) 表示选定 (k) 个元素的方案数。选定 (k) 个元素后，还剩下 (n-k) 个元素，即有 (2^{n-k}) 个集合可以选择，即有 (2^{2^{n-k}}-1) 种选择集合的方案（至少选一个集合，除去空集）。
设 (g(i)) 表示交集元素恰好为 (i) 个的方案数。因为选定 (k) 个交集元素后，实际的交集元素个数只会大于等于 (k) ，则有：
这就是一个典型的二项式反演的形式三，可以得到：
于是就可以 (O(n)) 求 (g(k)) 了。
( ext{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
",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 ({ m{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} imes (cnt-j+1)) 转移而来
综上有：
设 (f(m)) 表示至少有 (m) 个 (A_i>B_j) 的数对的方案数，(g(m)) 表示恰好有 (m) 个 (A_i>B_j) 的数对的方案数。则有：
因为除了指定的 (m) 个满足 (A_i>B_j) 的数对，(A) 中还有 (n-m) 个数可以与 (B) 中 (n-m) 个数自由组合，则有：
由二项式反演的形式三可得：
直接求这个和式即可。
( ext{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
",ans);
return 0;
}