1
容斥原理的式子：
\[|A1∪A2∪...∪An|=\sum_{1≤i≤n}|Ai|−\sum_{1≤i<j≤n}|Ai∩Aj|+...+(−1)^{n−1}×|A1∩A2∩...∩An| \]一般来说不会直接用容斥原理这个式子，而是考虑一种特殊情况：交集的大小只与交集的数量有关。也就是说，我们可以用\(f[x]\)来表示\(n\)个集合的交集的大小。
这样，这个式子就可以写成：
\[|A1∪A2∪...∪An|=\sum_{i=1}^n (-1)^{i-1}*C_i^n*f[i] \]一般使用这种形式来把一个复杂的式子化成一个相对简单的式子。
2
二项式反演的式子是根据补集的定义推出来的。
设\(g[x]\)表示\(x\)个补集的交集的大小，\(S\)为全集，那么有：
\[g[n]=|S|-\sum_{i=1}^n(-1)^{i-1}*C_i^n*f[i]=\sum_{i=0}^n(-1)^i*C_i^n*f[i] \]同时，补集的补集就是原集，此时也有：
\[f[n]=\sum_{i=0}^n(-1)^i*C_i^n*g[i] \]于是就有了二项式反演基本的式子。
3
二项式反演还有两个变形式：
- \(f[n]=\sum\limits_{i=m}^n C_i^n*g[i]\) 以及 \(g[n]=\sum\limits_{i=m}^n(-1)^{n-i}*C_i^n*f[i]\)
- \(f[n]=\sum\limits_{i=n}^m C_n^i*g[i]\) 以及 \(g[n]=\sum\limits_{i=n}^m(-1)^{i-n}*C_n^i*g[i]\)
两个变形式可以通过左面带入右面得证。
4
然后考虑组合意义。
\(f[i]表示n个数里选必须选某i个数的全部情况数。\)
\(g[i]表示n个数里满足条件的只有某i个数的全部情况数。\)
显然计算\(f[i]\)时必然会重复计算\(a\)次\(g[i]\)，而\(a\)恰好等于\(C_i^n\)，满足上面的式子。
那么我们就可以通过反演来利用相对好求的\(f[i]\)求出\(g[i]\)。
5
5.1
一个有\(n\)个元素的集合有\(2n\)个不同子集（包含空集），现在要在这\(2n\)个集合中取出至少一个集合，使得它们的交集的元素个数为\(k\)，求取法的方案数模\(10^9+7\)。
tip:板子
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long jc[1000010],bas[1000010];
const long long mod=1000000007;
inline long long ksm(long long base,long long zhi){
long long ans=1;
while(zhi){
if(zhi&1) ans=ans*base%mod;
zhi>>=1;
base=base*base%mod;
}
return ans;
}
void init(long long n){
jc[0]=1;
bas[0]=2;
for(long long i=1;i<=n;i++){
jc[i]=jc[i-1]*i%mod;
bas[i]=bas[i-1]*bas[i-1]%mod;
}
return;
}
long long C(long long n,long long m){
if(m>n) return 0;
return (jc[n]*ksm(jc[m]*jc[n-m]%mod,mod-2))%mod;
}
long long ans(long long n,long long k){
long long ll=0,x=-1;
for(long long i=k;i<=n;i++){
x=-x;
long long aa=C(i,k)*C(n,i)%mod*(bas[n-i]-1)%mod;
ll=ll+mod+x*aa;
ll%=mod;
}
return ll;
}
int main(){
long long n,k;
scanf("%lld%lld",&n,&k);
init(n);
printf("%lld",ans(n,k));
return 0;
}
5.2
给出两个长度均为\(n\)的序列\(A\)和\(B\)，保证这\(2n\)个数互不相同。现要将\(A\)序列中的数与\(B\)序列中的数两两配对，求“\(A>B\)的对数比\(A<B\)的对数恰好多\(k\)”的配对方案数模\(10^9+9\)。
tip:二维dp
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long jc[2010];
long long dp[2010][2010];
const long long mod=1000000009;
void init(){
jc[0]=1;
for(long long i=1;i<=2001;i++){
jc[i]=jc[i-1]*i%mod;
}
return;
}
inline long long ksm(long long base,long long zhi){
long long ans=1;
while(zhi){
if(zhi&1) ans=ans*base%mod;
zhi>>=1;
base=base*base%mod;
}
return ans;
}
long long C(long long n,long long m){
if(m>n) return 0;
return jc[n]*ksm(jc[m]*jc[n-m]%mod,mod-2)%mod;
}
long long a[2010],b[2010],c[2010];
int main(){
init();
memset(c,0,sizeof(c));
memset(dp,0,sizeof(dp));
long long n,k;
scanf("%lld%lld",&n,&k);
for(long long i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(long long i=1;i<=n;i++){
scanf("%lld",&b[i]);
}
if((n+k)%2!=0){
printf("0");
return 0;
}
long long as=(n+k)/2;
sort(a+1,a+n+1);
sort(b+1,b+n+1);
dp[0][0]=1;
for(long long i=1;i<=n;i++){
dp[i][0]=1;
for(long long j=1;j<=n;j++){
if(a[i]>b[j]) c[i]++;
}
for(long long j=1;j<=i;j++){
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(c[i]-j+1)%mod;
dp[i][j]%=mod;
}
}
long long ans=0,x=-1;
for(long long i=as;i<=n;i++){
x=-x;
long long aa=C(i,as)*jc[n-i]%mod*dp[n][i]%mod;
ans=ans+mod+x*aa;
ans%=mod;
}
printf("%lld",ans);
return 0;
}