二项式反演学习笔记

内容

钦定若干个条件满足,设为 \(g[k]\),将恰好的方案数设为 \(f[k]\)

则有\(g[k]=\sum_\limits{i=k}^nC_k^if(i)\)

根据二项式反演可以得到 \(f[k]=\sum\limits_{i=k}^n(-1)^{i-k}C_k^ig(i)\)

集合计数

题目传送门

分析

设钦定 \(k\) 个元素重合的方案数为 \(g[k]\)

则 \(g[k]=C_n^k \times (2^{2^{n-k}}-1)\)

含义为先选出 \(k\) 个元素

包含这 \(k\) 个元素的集合有 \(2^{n-k}\) 种

每种集合都可以选或者不选,但不能全都不选

代码

#include<cstdio>
#include<algorithm>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e6+5,mod=1e9+7;
int n,k,jc[maxn],ny[maxn],jcc[maxn],ans,g[maxn];
void pre(){
	ny[1]=1;
	for(rg int i=2;i<=n;i++) ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod;
	jc[0]=jcc[0]=1;
	for(rg int i=1;i<=n;i++){
		jc[i]=1LL*jc[i-1]*i%mod;
		jcc[i]=1LL*jcc[i-1]*ny[i]%mod;
	}
}
int getC(rg int nn,rg int mm){
	return 1LL*jc[nn]*jcc[mm]%mod*jcc[nn-mm]%mod;
}
int ksm(rg int ds,rg int zs,rg int Mod){
	rg int nans=1;
	while(zs){
		if(zs&1) nans=1LL*nans*ds%Mod;
		ds=1LL*ds*ds%Mod;
		zs>>=1;
	}
	return nans;
}
int main(){
	n=read(),k=read();
	pre();
	for(rg int i=0;i<=n;i++){
		g[i]=1LL*getC(n,i)*(ksm(2,ksm(2,n-i,mod-1),mod)-1)%mod;
	}
	for(rg int j=k;j<=n;j++){
		ans+=1LL*g[j]*((j-k&1)?(-1):1)*getC(j,k)%mod;
		ans=(ans>=mod)?(ans-mod):ans;
		ans=(ans<0)?(ans+mod):ans;
	}
	printf("%d\n",ans);
	return 0;
}

已经没有什么好害怕的了

题目传送门

分析

因为 \(a\) 大于 \(b\) 的要比 \(b\) 大于 \(a\) 的多 \(k\) 组

实际上就是 \(a\) 大于 \(b\) 的有 \(\frac{n+k}{2}\) 组

设 \(dp[i][j]\) 表示 \(a\) 考虑到了第 \(i\) 位,钦定了 \(j\) 组 \(a>b\) 的方案数,\(cnt[i]\) 为 \(b\) 数组中有多少个数比 \(a[i]\) 小

则 \(dp[i][j]=dp[i-1][j]+dp[i-1][j-1]\times(cnt[i]-j+1)\)

钦定了 \(j\) 组,剩下的 \(n-j\) 组就可以随便选

所以还要乘上一个 \((n-j)!\)

套一下上面的反演式子就可以了

代码

#include<cstdio>
#include<algorithm>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=2e3+5,mod=1e9+9;
int n,k,a[maxn],b[maxn],dp[maxn][maxn],cnt[maxn],jc[maxn],ny[maxn],jcc[maxn],f[maxn],g[maxn];
void pre(){
	ny[1]=1;
	for(rg int i=2;i<=n;i++) ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod;
	jc[0]=jcc[0]=1;
	for(rg int i=1;i<=n;i++){
		jc[i]=1LL*jc[i-1]*i%mod;
		jcc[i]=1LL*jcc[i-1]*ny[i]%mod;
	}
}
int getC(rg int nn,rg int mm){
	return 1LL*jc[nn]*jcc[mm]%mod*jcc[nn-mm]%mod;
}
int main(){
	n=read(),k=read();
	k=(n+k)/2;
	pre();
	for(rg int i=1;i<=n;i++) a[i]=read();
	for(rg int i=1;i<=n;i++) b[i]=read();
	std::sort(a+1,a+n+1);
	std::sort(b+1,b+n+1);
	for(rg int i=1;i<=n;i++) cnt[i]=std::upper_bound(b+1,b+1+n,a[i])-b-1;
	dp[0][0]=1;
	for(rg int i=1;i<=n;i++){
		dp[i][0]=1;
		for(rg int j=1;j<=n;j++){
			dp[i][j]=1LL*dp[i-1][j-1]*std::max(0,cnt[i]-j+1)%mod+dp[i-1][j];
			dp[i][j]=(dp[i][j]>=mod)?(dp[i][j]-mod):dp[i][j];
		}
	}
	for(rg int i=0;i<=n;i++){
		g[i]=1LL*dp[n][i]*jc[n-i]%mod;
	}
	for(rg int i=0;i<=n;i++){
		for(rg int j=i;j<=n;j++){
			f[i]+=1LL*g[j]*((j-i&1)?(-1):1)*getC(j,i)%mod;
			f[i]=(f[i]>=mod)?(f[i]-mod):f[i];
			f[i]=(f[i]<0)?(f[i]+mod):f[i];
		}
	}
	printf("%d\n",f[k]);
	return 0;
}

七选五

分析

设 \(g[i]\) 为钦定 \(i\) 个选对的方案数

则 \(g[i]=C_k^i \times C_{n-i}^{k-i} \times (k-i)!\)

含义为从答案序列中选出 \(i\) 个选对

然后从剩下的字母中随便选 \(k-i\) 个

因为可以调换顺序,所以要乘上阶乘

代码

#include<cstdio>
#include<algorithm>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e6+5,mod=1e9+7;
int n,k,x,jc[maxn],ny[maxn],jcc[maxn],ans,g[maxn];
void pre(){
	ny[1]=1;
	for(rg int i=2;i<=n;i++) ny[i]=1LL*(mod-mod/i)*ny[mod%i]%mod;
	jc[0]=jcc[0]=1;
	for(rg int i=1;i<=n;i++){
		jc[i]=1LL*jc[i-1]*i%mod;
		jcc[i]=1LL*jcc[i-1]*ny[i]%mod;
	}
}
int getC(rg int nn,rg int mm){
	return 1LL*jc[nn]*jcc[mm]%mod*jcc[nn-mm]%mod;
}
int ksm(rg int ds,rg int zs,rg int Mod){
	rg int nans=1;
	while(zs){
		if(zs&1) nans=1LL*nans*ds%Mod;
		ds=1LL*ds*ds%Mod;
		zs>>=1;
	}
	return nans;
}
int main(){
	n=read(),k=read(),x=read();
	pre();
	for(rg int i=0;i<=k;i++){
		g[i]=1LL*getC(k,i)*getC(n-i,k-i)%mod*jc[k-i]%mod;
	}
	for(rg int j=x;j<=k;j++){
		ans+=1LL*g[j]*((j-x&1)?(-1):1)*getC(j,x)%mod;
		ans=(ans>=mod)?(ans-mod):ans;
		ans=(ans<0)?(ans+mod):ans;
	}
	printf("%d\n",ans);
	return 0;
}
上一篇:「Violet」蒲公英


下一篇:「国家集训队」稳定婚姻