常见公式：
先给出几个重要的公式/结论：
一些常见的二项式反演：
(f_n=sum_{i=0}^{n}(-1)^iinom{n}{i}g_iRightarrow g_n=sum_{i=0}^{n}(-1)^iinom{n}{i}f_i)
(f_{n}=sum_{i=0}^{n}inom{n}{i}g_iRightarrow sum_{i=0}^{n}(-1)^{n-i}inom{n}{i}f_i)
(f_{k}=sum_{i=k}^{n}(-1)^iinom{i}{k}g_iRightarrow g_k= sum_{i=k}^{n}(-1)^iinom{i}{k}f_i)
(f_{k}=sum_{i=k}^{n}inom{i}{k}g_iRightarrow g_k=sum_{i=k}^{n}(-1)^{i-k}inom{i}{k}f_i)
证明什么的就先略过了~
广义容斥原理：
设全集元素个数为 (n)，(f(i)) 表示钦定 (i) 个为一组，其余 (n-i) 个元素随便弄得方案数，(g(i)) 表示恰好有 (i) 个发生的方案数. （可以去看分特产）
则有 (f(k)=sum_{i=k}^{n}inom{i}{k}g(i))
这是上面二项式反演的一种形式，直接反演，得:
(g_k=sum_{i=k}^{n}(-1)^{i-k}inom{i}{k}f_i)
所以，知道 (f) 的情况下可以用二项式反演求 (g)
如果 (f,g) 的维度很多的话那就对每一个维度都这么拆就行了（比如说后面 bzoj4487)
如果说 (g) 非常好求或者 (f) 的定义是 "正好" 的话就可以用普通的容斥原理搞来搞去了~
一些例题：
分特产 (luogu 5505)
共有 (m) 种物品，每个物品 (a[i]) 个，分给 (n) 个人，每个人至少要拿到一件，求方案数.
令 (f[i]) 表示钦定 (i) 个没分到特产，其余 ((n-i)) 个人随便选的方案数，(g[i]) 表示恰好 (i) 个没分到特产的方案数.
按照我们之前讲的，有 (f[k]=sum_{i=k}^{n}inom{k}{i}g[i]Rightarrow g[k]=sum_{i=k}^{n}(-1)^{i-k}inom{i}{k}f[i])
而根据定义，(f[i]=inom{n}{i} imes prod_{j=1}^{m}inom{a[j]+n-i-1}{n-i-1})
所以先预处理 (f[i])，然后求 (g[0]) 就好了（恰好 (0) 个人没分到特产的方案数）
code:
#include <bits/stdc++.h>
#define N 10005
#define LL long long
using namespace std;
const LL mod=1000000007;
void setIO(string s)
{
string in=s+".in";
string out=s+".out";
freopen(in.c_str(),"r",stdin);
}
int a[N];
LL fac[N],inv[N],f[N],g[N];
LL qpow(LL x,LL y)
{
LL tmp=1ll;
for(;y;y>>=1,x=x*x%mod)
if(y&1) tmp=tmp*x%mod;
return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
LL C(int x,int y)
{
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
// setIO("input");
int i,j,n,m;
fac[0]=inv[0]=1ll;
for(i=1;i<N;++i) fac[i]=fac[i-1]*1ll*i%mod,inv[i]=Inv(fac[i]);
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i) scanf("%d",&a[i]);
for(i=0;i<=n;++i)
{
f[i]=C(n,i);
for(j=1;j<=m;++j) (f[i]=f[i]*C(a[j]+n-i-1,n-i-1)%mod)%=mod;
}
for(i=0;i<=n;++i)
{
(g[0]+=qpow(-1,i)*f[i]%mod+mod)%=mod;
}
printf("%lld
",g[0]);
return 0;
}
集合计数 (BZOJ 2839)
在一个 (N) 个元素集合中的所有子集中选择若干个，且交集大小为 (k) 的方案数.
按照之前的套路，令 (f[k]) 表示钦定交集大小为 (k)，其余随便选的方案数. 令 (g[k]) 表示交集恰好为 (k) 的方案数.
则有 (f[k]=sum_{i=k}^{n}inom{i}{k}g[k])，反演得 (g[k]=sum_{i=k}^{n}(-1)^{i-k}inom{i}{k}f[i])
而 (f[k]=inom{n}{k}2^{2^{n-k}})，直接带入求值即可.
code:
#include <bits/stdc++.h>
#define N 1000005
#define LL long long
using namespace std;
const LL mod=1000000007;
void setIO(string s)
{
string in=s+".in";
string out=s+".out";
freopen(in.c_str(),"r",stdin);
}
int a[N];
LL fac[N],inv[N],f[N],g[N],poww[N];
LL qpow(LL x,LL y)
{
LL tmp=1ll;
for(;y;y>>=1,x=x*x%mod)
if(y&1) tmp=tmp*x%mod;
return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
LL C(int x,int y)
{
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
// setIO("input");
int i,j,n,k;
fac[0]=inv[0]=poww[0]=1ll;
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i)
fac[i]=fac[i-1]*1ll*i%mod,inv[i]=Inv(fac[i]),poww[i]=poww[i-1]*2ll%(mod-1);
for(i=0;i<=n;++i)
f[i]=C(n,i)*qpow(2,poww[n-i])%mod;
LL ans=0ll;
for(i=k;i<=n;++i)
(ans+=(qpow(-1,i-k)*C(i,k)%mod*f[i]%mod+mod)%mod)%=mod;
printf("%lld
",ans);
return 0;
}
小w的喜糖 (BZOJ 4665 )
小w一共买了 (n) 块喜糖，发给了 (n) 个人，每个喜糖有一个种类。这时，小w突发奇想，如果这n个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。
还是考虑容斥：为了方便，我们将同一种糖果也依次编号，这样在计算时候会简便一些.
令 (f[i][j]) 表示考虑前 (i) 种糖果，(j) 个人拿到同种糖果的方案数.
则有转移：(f[i][j]=sum_{k=0}^{min(j,cnt[i])}f[i-1][j-k] imes inom{cnt[i]}{k} imes A_{cnt[i]}^{k})
考虑这个转移的组合意义：我们在 (i) 糖果中强制选择 (k) 个人拿同样的糖果，为 (inom{cnt[i]}{k})
而每一个人分别有：(cnt[i],cnt[i]-1,......) 种选择，即总共是 (A_{cnt[i]}^{k}) 种选糖方案（编号不同）
那么选择人的方案 $ imes $ 选择糖的方案 = (i) 种糖中选择 (k) 个人，每个人都拿自己种类的方案数.
得到 (f[n][i]) 后，让其他 ((n-i)) 个人随便选，即 (f[n][i] imes (n-i)!Rightarrow f[n][i])
推出 (f[n][i]) 后就简单了（这个组合意义是强制让 (i) 个人拿到自己糖的组合方案）
直接上二项式反演，得 (g[0]=sum_{i=0}^{n}(-1)^i imes f[n][i])
别忘了，最后还有除一下阶乘，因为我们把每个糖得不同编号也看作不同了~
code:
#include <bits/stdc++.h>
#define N 2005
#define LL long long
using namespace std;
const LL mod=1000000009;
void setIO(string s)
{
string in=s+".in";
freopen(in.c_str(),"r",stdin);
}
int cnt[N],sum[N];
LL fac[N],inv[N],f[N][N];
LL qpow(LL x,LL y)
{
LL tmp=1ll;
for(;y;y>>=1,x=x*x%mod)
if(y&1) tmp=tmp*x%mod;
return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
LL C(int x,int y) { return fac[x]*inv[y]%mod*inv[x-y]%mod; }
LL A(int x,int y) { return fac[x]*inv[x-y]%mod; }
int main()
{
// setIO("input");
int i,j,n,k;
scanf("%d",&n);
fac[0]=inv[0]=1ll;
for(i=1;i<=n;++i) fac[i]=fac[i-1]*1ll*i%mod,inv[i]=qpow(fac[i],mod-2);
for(i=1;i<=n;++i)
{
int x;
scanf("%d",&x),++cnt[x];
}
for(i=1;i<=n;++i) sum[i]=sum[i-1]+cnt[i];
f[0][0]=1ll;
for(i=1;i<=n;++i)
{
for(j=0;j<=sum[i];++j)
{
for(k=0;k<=min(cnt[i],j);++k)
(f[i][j]+=f[i-1][j-k]*C(cnt[i],k)%mod*A(cnt[i],k)%mod)%=mod;
}
}
LL ans=0ll;
for(i=0;i<=n;++i)
{
LL d=(i&1)?-1:1;
(ans+=(d*f[n][i]%mod+mod)*fac[n-i]%mod)%=mod;
}
for(i=1;i<=n;++i) ans=ans*inv[cnt[i]]%mod;
printf("%lld
",ans);
return 0;
}
毒瘤选举
有 (n) 个选民和 (m) 个候选人，每个选民只能投一张票，求有多少种方案使得每个候选人至少得到一张选票.
考虑容斥：令 (f[k]) 表示钦定 (k) 个候选人得不到选票的方案数，(g[k]) 表示恰好 (k) 个得不到选票的方案数.
那么有 (f[k]=inom{m}{k} imes (m-k)^n)
而依据定义，(f[k]=sum_{i=k}^{m}inom{i}{k} imes g[i])
二项式反演，得 (g[k]=sum_{i=k}^{m}(-1)^{i-k}inom{i}{k} imes f[i])，带入求值即可.
原题的话模数是一个合数，但是可以被拆成若干个互不相同质数的乘积，需要用扩展CRT，这里就让模数是质数.
code:
#include <bits/stdc++.h>
#define N 10005
#define LL long long
using namespace std;
void setIO(string s)
{
string in=s+".in";
freopen(in.c_str(),"r",stdin);
}
const LL mod=1000000007;
LL fac[N],inv[N],f[N];
LL qpow(LL x,LL y)
{
LL tmp=1ll;
for(;y;y>>=1,x=x*x%mod)
if(y&1)
tmp=tmp*x%mod;
return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
LL C(int x,int y) { return fac[x]*inv[y]%mod*inv[x-y]%mod; }
int main()
{
// setIO("input");
int i,j,n,m;
fac[0]=inv[0]=1ll;
for(i=1;i<N;++i) fac[i]=fac[i-1]*1ll*i%mod,inv[i]=Inv(fac[i]);
scanf("%d%d",&n,&m);
for(i=0;i<=m;++i)
f[i]=C(m,i)*qpow(m-i,n)%mod;
LL ans=0ll;
for(i=0;i<=m;++i)
{
LL d=(i&1)?-1:1;
(ans+=(d*f[i]%mod+mod)%mod)%=mod;
}
printf("%lld
",ans);
return 0;
}
染色问题 （BZOJ 4487）
给定 (n imes m) 的棋盘和 (c) 种颜色，要求对棋盘染色且每一行，每一列至少要被染上一种颜色，且 (c) 种颜色都要用上.
求方案数模 (10^9+7)
还是和以前一样，列 (f_{i,j,k}) 表示钦定 (i) 行 (j) 列未染色，(k) 种颜色未用上的方案数.
(f_{i,j,k}=inom{n}{i}inom{m}{j}inom{c}{k}(c-k+1)^{(n-i)(m-j)})
令 (g_{i,j,k}) 表示恰好的方案数，但是发现这个是 (3) 维的，而上面的都是二维的.
这里直接给出多维的容斥公式：
(g_{i,j,k}=sum_{x=i}^{n}sum_{y=j}^{m}sum_{l=k}^{c}(-1)^{l-k+x-i+y-j}inom{l}{k}inom{x}{i}inom{y}{j}f_{x,y,l})
这里 (i,j,k) 都等于 (0)，直接套用即可.
code:
#include <bits/stdc++.h>
#define N 504
#define LL long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const LL mod=1000000007;
LL fac[N],inv[N],poww[N*N];
LL qpow(LL x,LL y)
{
LL tmp=1ll;
for(;y;y>>=1,x=x*x%mod)
if(y&1)
tmp=tmp*x%mod;
return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
LL C(int x,int y) { return fac[x]*inv[y]%mod*inv[x-y]%mod; }
int main()
{
// setIO("input");
int n,m,c,i,j;
scanf("%d%d%d",&n,&m,&c);
fac[0]=inv[0]=1ll;
for(i=1;i<N;++i) fac[i]=fac[i-1]*1ll*i%mod,inv[i]=Inv(fac[i]);
LL ans=0ll;
for(int k=0;k<=c;++k)
{
poww[0]=1ll;
for(i=1;i<=n*m;++i) poww[i]=poww[i-1]*1ll*(c-k+1)%mod;
for(i=0;i<=n;++i)
for(j=0;j<=m;++j)
{
LL d=((i+j+k)&1)?-1:1;
(ans+=(C(n,i)*C(m,j)%mod*C(c,k)%mod*poww[(n-i)*(m-j)]%mod*d+mod)%mod)%=mod;
}
}
printf("%lld
",ans);
return 0;
}
染色（luogu 4491)
给定长度为 (n) 的序列, 每个位置都可以被染成 (m) 种颜色中的某一种. 如果恰好出现了 (s) 次的颜色有 (k) 种, 则会产生 (w_{k}) 的价值. 求对于所有可能的染色方案，获得价值和对 (1004535809) 取模的结果.
设 (lim=min(m,frac{n}{s}))，即最大可能的颜色出现种类.
按照套路，令 (f[i]) 表示钦定 (i) 种长度为 (s) 出现的方案数，(g[i]) 表示恰好 (i) 种出现的方案数.
(f[k]=inom{m}{k}frac{n!}{(n-ks)!(s!)^k}(m-k)^{n-ks})
组合意义就是选 (ks) 个位置放出现次数为 (s) 的颜色，然后其余部分随便放.
而 (g[k]=sum_{i=k}^{lim}inom{i}{k}(-1)^{i-k}f[i])
因为我们要算贡献，所以要求 (g[1]....g[lim]) ，而上面的式子是 (O(lim^2)) 的.
考虑优化：
将上面 (inom{i}{k}) 展开，得 (g[k]=frac{1}{k!}sum_{i=k}^{lim} frac{(-1)^{i-k}}{(i-k)!}f[i] imes i!)
令 (a[i]=frac{(-1)^i}{i!})，(b[i]=f[i] imes i!) ，则 (g[k]=frac{1}{k!}sum_{i=k}^{lim} a[i-k] imes b[i])
这是一个标准的卷积形式！
直接用 NTT 加速即可.
#include <bits/stdc++.h>
#define N 800005
#define LL long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const LL G=3;
const LL mod=1004535809;
LL A[N],B[N],Ct[N],f[N],g[N],fac[10000008],inv[10000007],val[N];
LL qpow(LL x,LL y)
{
LL tmp=1ll;
for(;y;y>>=1,x=x*x%mod)
if(y&1)
tmp=tmp*x%mod;
return tmp;
}
LL Inv(LL x) { return qpow(x,mod-2); }
void NTT(LL *a,int n,int flag)
{
int i,j,k,mid;
for(i=k=0;i<n;++i)
{
if(i>k) swap(a[i],a[k]);
for(j=n>>1;(k^=j)<j;j>>=1);
}
for(mid=1;mid<n;mid<<=1)
{
LL wn=qpow(G,(mod-1)/(mid<<1));
if(flag==-1) wn=Inv(wn);
for(i=0;i<n;i+=(mid<<1))
{
LL w=1ll;
for(j=0;j<mid;++j)
{
LL x=a[i+j],y=w*a[i+mid+j]%mod;
a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;
w=w*wn%mod;
}
}
}
if(flag==-1)
{
LL re=Inv(n);
for(i=0;i<n;++i) a[i]=a[i]*re%mod;
}
}
LL C(int x,int y) { return fac[x]*inv[y]%mod*inv[x-y]%mod; }
int main()
{
// setIO("input");
int n,m,s,i,j,lim;
scanf("%d%d%d",&n,&m,&s);
for(i=0;i<=m;++i) scanf("%lld",&val[i]);
lim=min(m,n/s);
inv[0]=fac[0]=1ll;
int pp=max(n,m);
for(i=1;i<=pp;++i)
{
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[max(n,m)]=qpow(fac[max(n,m)],mod-2);
for(i=max(n,m)-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
for(i=0;i<=lim;++i)
{
f[i]=C(m,i)*fac[n]%mod*inv[n-i*s]%mod*qpow(inv[s],i)%mod*qpow(m-i,n-i*s)%mod*fac[i]%mod;
}
for(i=0;i<=lim;++i) A[i]=(inv[i]*(i&1?-1:1)+mod)%mod;
for(i=0;i<=lim;++i) B[lim-i]=f[i];
LL ans=0ll;
int tmp=1;
while(tmp<=lim*2) tmp<<=1;
NTT(A,tmp,1),NTT(B,tmp,1);
for(i=0;i<tmp;++i) Ct[i]=A[i]*B[i]%mod;
NTT(Ct,tmp,-1);
for(i=0;i<=lim;++i) g[i]=Ct[lim-i]*inv[i]%mod;
for(i=0;i<=lim;++i)
{
(ans+=g[i]*val[i]%mod)%=mod;
}
printf("%lld
",ans);
return 0;
}
第二类斯特林数
这个的推导过程会用到二项式反演.
令 (S(n,m)) 表示将 (n) 个互不相同的元素装进 (m) 个相同盒子，且盒子不能为空的方案数.
朴素递推：(S(n,m)=S(n-1,m-1)+S(n-1,m) imes m)
因为盒子不为空，所以第一种情况只能放入最新的盒子，而第二种情况的话 (m) 个盒子可以随便放.
这个太慢了，考虑二项式反演：
假设 (n) 固定，我们要求 (S(n,m)) ，则令 (f[k]) 表示钦定 (k) 个盒子为空，其余随便选的方案，(g[k]) 表示恰好.
则有 (f[k]=inom{m}{k}(m-k)^n=sum_{i=k}^{m}inom{i}{k}g[i])
反演，得 (g[0]=sum_{i=0}^{m}(-1)^if[i]).
注意：这里实际上默认将不同得盒子看作不同，所以还要除一个阶乘.
那么，就有 (S(n,m)=frac{1}{m!}sum_{i=0}^{m}(-1)^iinom{m}{i}(m-i)^n)
我们把组合数展开，然后约掉最外面的 (frac{1}{m!}) 就会得到：(S(n,m)=sum_{i=0}^{m}frac{(-1)^i}{i!}frac{(m-i)^n}{(m-i)!})
这个用 NTT 加速多项式乘法来算即可.
#include <bits/stdc++.h>
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n;
const ll mod=167772161,G=3,N=400006;
ll f[N<<1],g[N<<1],fac[N],inv[N];
ll qpow(ll x,ll y)
{
ll tmp=1ll;
while(y)
{
if(y&1) tmp=tmp*x%mod;
y>>=1,x=x*x%mod;
}
return tmp;
}
void NTT(ll *a,int len,int flag)
{
int i,j,k,mid;
for(i=k=0;i<len;++i)
{
if(i>k) swap(a[i],a[k]);
for(j=len>>1;(k^=j)<j;j>>=1);
}
for(mid=1;mid<len;mid<<=1)
{
ll wn=qpow(G,(mod-1)/(mid<<1));
if(flag==-1) wn=qpow(wn,mod-2);
for(i=0;i<len;i+=(mid<<1))
{
ll w=1ll;
for(j=0;j<mid;++j)
{
ll x=a[i+j],y=w*a[i+mid+j]%mod;
a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;
w=w*wn%mod;
}
}
}
if(flag==-1)
{
ll re=qpow(len,mod-2);
for(i=0;i<len;++i) a[i]=a[i]*re%mod;
}
}
int main()
{
// setIO("input");
scanf("%d",&n);
fac[0]=1ll;
inv[0]=1ll;
int i,j,limit=1;
for(i=1;i<=n;++i) fac[i]=fac[i-1]*1ll*i%mod, inv[i]=qpow(fac[i],mod-2);
for(i=0;i<=n;++i)
{
g[i]=qpow(i,n)*inv[i]%mod;
if(i&1) f[i]=mod-inv[i];
else f[i]=inv[i];
}
for(;limit<=2*(n+1);limit<<=1);
NTT(f,limit,1),NTT(g,limit,1);
for(i=0;i<limit;++i) f[i]=f[i]*g[i]%mod;
NTT(f,limit,-1);
for(i=0;i<=n;++i) printf("%lld ",f[i]);
return 0;
}