前(fei)言(hua)
高二学长说CTS2019D1T1可以用二项式反演推容斥系数，但我当时是找规律找出来的。。。
后来遇到一道类似的题才推了出来，然后知道了这就是二项式反演。。。
然后发现网上的博客都只写了证明啊。。。
下面就讲一下二项式反演是怎么来的
二项式定理（讲得这么高大上其实就是一句废话）
遇到(sum_{i=0}^k(-1)^iC_k^i)的时候可以补上一个(1^{k-i})然后倒着用二项式定理，最后可以化简为(0^k)。
容斥原理（小学数学复习）
小学经常见到的那张图
回顾一下小学学过的容斥原理：
其中(S)为三种属性，一个物品可以表示成一个属性的集合，(ABCDEFG)为一些属性集合相同的物品组成的集合。
比如：一个学生参加了活动(S1)和(S2)，他的属性集合可以被表示为({S1,S2})，所以他属于集合(D)。
一个经典小学数学问题
小学数学中的一个经典问题是：知道所有至少具有属性S1的物品数和（(S2,S3)类似）、至少具有(S1)和(S2)属性的物品数（(S1)和(S3)，(S2)和(S3)类似）和同时具有(S1,S2,S3)属性的物品数，求所有物品的数量。
我们定义(X1,X2,X3)分别为至少具有(S1,S2,S3)属性的物品的集合，那么(X1=A+D+E+G,X1cap X2=D+G)，以此类推。
问题可以表示为：知道(|X1|,|X2|,|X3|,|X1cap X2|,|X1cap X3|,|X2cap X3|,|X1cap X2cap X3|)，求(|X1cup X2cup X3|)。
我们小学的时候就知道答案是至少一个属性的物品数量-至少两个属性的+至少三个的，即(|X1|+|X2|+|X3|-|X1cap X2|-|X1cap X3|-|X2cap X3|+|X1cap X2cap X3|)。因为(|X1|+|X2|+|X3|)把两个属性的物品多加了一次，所以要减去。然后我们发现三个属性的物品加了三次又被减了一次，所以我们要把它加回去。
如果考虑的属性更多会怎样
考虑属性更多的情况，我们可以做出假设：
证明：
考虑一个在(k)个集合中的元素((k>0))放在上面的例子中就是有(k)种属性的物品）被计算了多少次，假如我们把(i)个集合求交，这样的交显然是(C_k^i)个，所以我们可以枚举(i)。
这就是容斥原理。
子集反演（听说是叫这个但是我喜欢叫它容斥）
另一个经典小学数学问题
条件还是一样：对于每个属性集合，我们知道至少包含它的物品个数。我们现在要求只有某种属性的物品个数。
以(S1)为例，答案就是((A+D+E+G)-(D+G)-(E+G)+(G))，可以感性理解为至少包含一个的-至少包含两个的+至少包含三个的。
把(S1)改成({S1,S2})上述方法也适用。
我们用(f(X))表示(X)的超集的权值和（本例中权值就是属性集合为这个集合的物品数），(g(X))表示集合(X)的权值。
即$$f(S)=sum_{Tsupseteq S} g(T)$$
在本例中，(g(A)=f(A)-f(D)-f(E)+f(G))。
我们可以发现：$$g(S)=sum_{Tsupseteq S} (-1)^{|T|-|S|}f(T)$$
其意义很好理解，证明就代进去稍微化简一下就行了。
还有一个经典小学数学问题
(f(X))表示(X)的子集的权值和，(g(X))表示集合(X)的权值。
(g(G)=f(G)-f(D)-f(E)-f(F)+f(A)+f(B)+f(C))
然后发现：
比上一个还简单，留给读者自己思考。
二项式反演
一种形式
我们知道$$f(S)=sum_{Tsubseteq S} g(T)Leftrightarrow g(S)=sum_{Tsubseteq S} (-1)^{|S|-|T|}f(T)$$
如果集合的权值只和大小有关，用(f(|S|))代替(f(S))，(g(|S|))代替(g(S))：$$f(n)=sum_{i=0}^n C_n^ig(i)Leftrightarrow g(n)=sum_{i=0}^n (-1)^{n-i}C_n^if(i)$$
（(n)个元素的集合的大小为(i)的子集个数显然是(C_n^i)）
不信的话可以代进去验证一下。
另一种形式
令(f(n)=sum_{|S|=n} f(S),g(n)=sum_{|S|=n} g(S))，则
同理$$g(n)=sum_{i=n}^m (-1)^{i-n}C_i^nf(i)$$
所以$$f(n)=sum_{i=n}^mC_i^ng(i)Leftrightarrow g(n)=sum_{i=n}^m (-1)^{i-n}C_i^nf(i)$$
按理来说应该还有两种形式，不知道有没有用。
别人博客里写的基本形式
把(-1)乘到(g)里面就是第一种形式了（不知道这是拿来干嘛的）。
bzoj3622
题目大意
给两个长度为(n)的序列(A,B)，把其中的数两两配对，求(A)中的数大于(B)中的数恰好有(k)对的方案数对(10^9+9)取模的结果，(nleq 2000)。
题解
首先可以(dp)出(k)对合法剩下乱放的方案数，然后套一下上面所说的第二种形式就行了。
（实在不懂的话就是把一个配对方案表示成一个合法配对的集合，一个集合的权值就是能够表示成它的方案数。(k)个合法配对剩下乱配对的方案数就是这(k)个元素组成的集合的超集的权值和，(dp)值的意义就是所有大小为(k)的集合的这个值之和；我们最后要求的答案就是所有大小恰好为(k)的集合的权值和）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=4096,md=1000000009;
int n,k,a[mxn],b[mxn],f[mxn],c[mxn][mxn];
int main()
{
scanf("%d%d",&n,&k);
if ((n+k)&1) return puts("0"),0;
k=(n+k)>>1;
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for (int i=1;i<=n;++i) scanf("%d",&b[i]);
sort(b+1,b+n+1);
f[0]=1;
for (int i=1,cur=0;i<=n;++i){
for (;cur<n&&b[cur+1]<a[i];++cur);
for (int j=i;j;--j)
f[j]=(f[j]+f[j-1]*(cur-j+1ll))%md;
}
for (int i=n-1,num=1;i>=0;--i)
num=1ll*num*(n-i)%md,f[i]=1ll*f[i]*num%md;
for (int i=0;i<=n;++i) c[i][0]=1;
for (int i=1;i<=n;++i)
for (int j=1;j<=i;++j)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%md;
int ans=0;
for (int i=k,flg=1;i<=n;++i,flg=-flg)
ans=(ans+1ll*flg*c[i][k]*f[i])%md;
printf("%d
",(ans+md)%md);
return 0;
}