二项式反演

二项式反演

二项式反演 - 形式1

二项式反演 - 形式2

证明1 - 容斥原理

熟知容斥原理：

令 \(f_\geqslant(T)=f(i),f_=(T)=g(i)\)，即得

证毕

证明2 - 代数法

首先我们证明形式1

证毕

然后我们来证明形式二

证毕

相关应用

有了二项式反演，我们就可以很方便而又清晰的讨论一些容斥式子

奇奇怪怪的容斥限制就基本不会影响你分析题目

BZOJ2839 集合计数

题目分析

要求选定集合的交集恰好为 \(k\)，并不是很好考虑，但是我们可以考虑至少为 \(k\) 的情况

不难想到，只要我们能保证我们选出来的集合的交集中有我们知道的某 \(k\) 个数，那么剩下的怎么选都是合法的

于是我们强制选定 \(k\) 个元素，即为交集必定会有的那 \(k\) 个，方法数 \(\dbinom n k\)

然后剩下的数的幂集中随便选，即选择一个子集，方法数 \(2^{2^{n-i}}-1\)

我们设一个函数 \(g(i)\) 来表示这个，即 \(g(i)=\dbinom n k(2^{2^{n-i}}-1)\)

然后我们就可以考虑正好为 \(k\) 个时的情况的方案数 \(f(i)\)

不难发现 \(g(k)\) 其实就是 \(i\ge k\) 时，\(f(i)\) 的选取方式加起来，并且 \(i\) 在上指标的位置，即 \(g(k)=\sum\limits_{i=k}^n\dbinom i kf(i)\)

这显然是一个二项式反演的形式，大力反演即得 \(f(k)=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{n}{k}\dbinom{n-k}{i-k}(2^{2^{n-i}}-1)\)（二项式系数做了一个小小的变换）

注意事项

如果您最后的乘法写成了 \(f(k)=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{n}{k}\dbinom{n-k}{i-k}2^{2^{n-i}}\) 当然在bzoj上也是能A掉的，不过您可以试试这组数据：
in: 768 768
out: 1
wrong answer: 2

这是因为选择空集和全部不选效果是一样的

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 1000001
#define M 5001
#define INF 1100000000
#define Kafuu return
#define Chino 0
#define fx(l,n) inline l n
#define set(l,n,ty,len) memset(l,n,sizeof(ty)*len)
#define cpy(f,t,ty,len) memcpy(t,f,sizeof(ty)*len)
#define int long long
#define R register
#define C const
using namespace std;
C int mod=1e9+7;
int n,k,ans,bf,texp[N],fac[N];
fx(int,gi)(){
	R char c=getchar();R int s=0,f=1;
	while(c>'9'||c<'0'){
		if(c=='-') f=-f;
		c=getchar();
	}
	while(c<='9'&&c>='0') s=(s<<3)+(s<<1)+(c-'0'),c=getchar();
	return s*f;
}
fx(int,fpow)(int a,int b=mod-2){
	int sum=1;
	while(b){
		if(b&1) (sum*=a)%=mod;
		(a*=a)%=mod;
		b>>=1;
	}
	return sum;
}
fx(int,binom)(int up,int down){
	return fac[up]*fpow(fac[down])%mod*fpow(fac[up-down])%mod;
}
signed main(){
	n=gi(),k=gi();
	texp[0]=2;fac[0]=1;
	for(R int i=1;i<=n;i++){
		texp[i]=texp[i-1]*texp[i-1]%mod;
		fac[i]=fac[i-1]*i%mod;
	}
	for(R int i=k;i<=n;i++){
		bf=0;
		bf+=(texp[n-i]-1)*binom(n,k)%mod*binom(n-k,i-k);
		if((i-k)%2) bf=-bf;
		(ans+=bf+mod)%=mod;
	}
	printf("%lld",ans);
}

P5505 [JSOI2011]分特产

题目分析

每个人至少分得一个特产不就是恰好每个人都分得特产么

老套路，设 \(f(i)\) 为至少 \(i\) 个人没有特产，\(g(i)\) 为恰好 \(i\) 个人没有特产

我们对每个特产顺次分配，发现这个过程就是解一个方程：

其中 \(n_i\) 为第 \(i\) 种特产的数量，我们要求的即为这个方程的非负整数解的个数

立即得：\(f(k)=\dbinom n k\prod\limits_{i=1}^m\dbinom{n_i+n-k-1}{n+k-1}\)

然后我们和 \(g\) 联立一下，\(f(i)=\sum\limits_{j=i}^n\dbinom j if(j)\)

大力二项式反演：\(g(0)=\sum\limits_{i=0}^n(-1)^if(i)=\sum\limits_{i=0}^n(-1)^i\dbinom n i\prod\limits_{j=1}^m\dbinom{n_j+n-i-1}{n+i-1}\)

直接做就可以了，后面是可以预处理的，但是处不处理都能过

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 1000001
#define M 5001
#define INF 1100000000
#define Kafuu return
#define Chino 0
#define fx(l,n) inline l n
#define set(l,n,ty,len) memset(l,n,sizeof(ty)*len)
#define cpy(f,t,ty,len) memcpy(t,f,sizeof(ty)*len)
#define int long long
#define R register
#define C const
using namespace std;
C int mod=1e9+7;
int n,m,v[N],ans,bf,fac[N];
fx(int,gi)(){
	R char c=getchar();R int s=0,f=1;
	while(c>'9'||c<'0'){
		if(c=='-') f=-f;
		c=getchar();
	}
	while(c<='9'&&c>='0') s=(s<<3)+(s<<1)+(c-'0'),c=getchar();
	return s*f;
}
fx(int,fpow)(int a,int b=mod-2){
	int sum=1;
	while(b){
		if(b&1) (sum*=a)%=mod;
		(a*=a)%=mod;
		b>>=1;
	}
	return sum;
}
fx(int,binom)(int up,int dn){
	return fac[up]*fpow(fac[up-dn])%mod*fpow(fac[dn])%mod;
}
signed main(){
	n=gi(),m=gi();
	for(R int i=1;i<=m;i++) v[i]=gi();
	fac[0]=1;
	for(R int i=1;i<=100000;i++) fac[i]=fac[i-1]*i%mod;
	for(R int i=0;i<=n;i++){
		bf=1;
		for(R int o=1;o<=m;o++) (bf*=binom(v[o]+n-i-1,n-i-1))%=mod;
		(bf*=binom(n,i))%=mod;
		if(i%2) bf=-bf;
		(ans+=mod+bf)%=mod;
	}
	printf("%lld",ans);
}

P4859 已经没有什么好害怕的了

我害怕儒略日，还害怕你出毒瘤题

题目分析

由之前的套路，我们只需要求出一个 \(f(i)\)，表示 \(n\) 个数中糖果比药片能量大的组数至少为 \(i\) 的方案数

而在这道题目中，\(f(i)\) 并不可用常规的组合式子表示出来

我们发现如果知道前 \(n-1\) 组的 \(f(i),f(i-1)\) 函数值就能很方便表示 \(n\) 组时的 \(f(i)\)

计算方式跟动态规划一样，于是我们设 \(f_{i,j}\)，表示前 \(i\) 组至少有 \(j\) 组被配对了的方案数

显然有 \(f_{i,j}=f_{i-1,j}+xf_{i-1,j-1}\)

\(x\) 怎么表示出来呢，不难想到如果这一组被配对成功了，那么在药片组里选择的一定是能量比其小的

我们并不知道，即使知道了也没有记录，即使记录了也不能很好处理前 \(j-1\) 组中被选择的

似乎陷入了困境

但是题目中求的只是方案数，也就是说不管你动态规划怎么循环，正序倒序欧拉序dfs序都是可以的

于是将其进行排序

如果从大至小排序，那么依然不好统计，我们选择将两个数组从小至大排序

这样，设 \(Y_i\) 表示 \(B\) 中小于 \(A_i\) 的元素的个数，立即可得

然后求 \(f(i)\) 与 \(g(i)\) 的关系式：

这是个裸的二项式反演，答案即为

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 1000001
#define M 3001
#define INF 1100000000
#define Kafuu return
#define Chino 0
#define fx(l,n) inline l n
#define set(l,n,ty,len) memset(l,n,sizeof(ty)*len)
#define cpy(f,t,ty,len) memcpy(t,f,sizeof(ty)*len)
#define int long long
#define R register
#define C const
using namespace std;
C int mod=1e9+9;
int n,k,A[N],B[N],ans,dp[M][M],les[N],m,fac[N],bf;
fx(int,gi)(){
	R char c=getchar();R int s=0,f=1;
	while(c>'9'||c<'0'){
		if(c=='-') f=-f;
		c=getchar();
	}
	while(c<='9'&&c>='0') s=(s<<3)+(s<<1)+(c-'0'),c=getchar();
	return s*f;
}
fx(int,fpow)(int a,int b=mod-2){
	int sum=1;
	while(b){
		if(b&1) (sum*=a)%=mod;
		(a*=a)%=mod;
		b>>=1;
	}
	return sum;
}
fx(int,binom)(int up,int down){
	return fac[up]*fpow(fac[up-down])%mod*fpow(fac[down])%mod;
}
signed main(){
	n=gi(),k=gi();m=(n+k)/2;
	if((n+k)&1) Kafuu Chino&printf("0");
	for(R int i=1;i<=n;i++) A[i]=gi();
	for(R int i=1;i<=n;i++) B[i]=gi();
	fac[0]=1;
	for(R int i=1;i<=10000;i++) fac[i]=fac[i-1]*i%mod;
	sort(A+1,A+n+1);sort(B+1,B+n+1);
	for(R int i=0;i<=n;i++) dp[i][0]=1;
	for(R int i=1,o=1;i<=n;i++){
		les[i]=les[i-1];
		while(o<=n&&B[o]<A[i]) les[i]+=1,o+=1;
	}
	for(R int i=1;i<=n;i++)
		for(R int o=1;o<=i;o++)
			dp[i][o]=(dp[i-1][o]+dp[i-1][o-1]*(les[i]-o+1)%mod)%mod;
	for(R int i=m;i<=n;i++){
		bf=0;
		bf=binom(i,m)*fac[n-i]%mod*dp[n][i]%mod;
		if((i-m)%2) bf=-bf;
		(ans+=bf+mod)%=mod;
	}
	Kafuu Chino&printf("%lld",ans);
}