在很多情况下，“恰好”往往是不好求的，因为恰好意味着"$\le$"并且"$\ge$"，需要进行很多限制，破坏了情况之间的独立性。

二项式反演则通过一定手段，使得限制"$\le$"与"$\ge$"中只保留一个，使得情况独立，便于处理。

二项式定理：

推论：

二项式反演公式：

证明一下：
只证明左边到右边。仿照证明过程容易证明右边到左边。

注意到若$j>i$，则${(}_j^i)=0$，可扩大枚举范围：

当然这里有一个非常有意思的地方就是，一些地方的证明中有如下过程：
$\stackrel{k}{\sum _{i=0}}\stackrel{i}{\sum _{j=0}}=\stackrel{k}{\sum _{j=0}}\stackrel{j}{\sum _{i=0}}$

这是在描述，把被和式求值的部分看做一个三角矩阵，左边是先对行求和，右边是先对列求和。

QED.

设$f(i)$表示至多有i个位置排错的方案数，$g(i)$表示恰好有i个位置排错的方案数。

显然“i”可分，有n个位置，就会有n-1个位置，n-2个位置…，显然分出来的"位置"本质不同，例如两个位置，可以是前两个位置，也可以是第1、第3个位置。

则有：

因而有：

注意到$f(i)$是非常好求的，因为至多有$i$个位置排错就相当于全排列。即$f(i)=i!$

因此就可以了。

#include<iostream>
using namespace std;
long long p[25];
int n;
int main() {
	p[0]=1;
	for(int i=1;i<=20;i++) p[i]=p[i-1]*i;
	cin>>n;
	long long ans=0;
	for(int i=0;i<=n;i++)
		ans+=p[n]/p[i]*(i&1?-1:1);
	cout<<ans;
	return 0;
}
实现上对式子做了一些变换

题目所说同一种的特产是无标号的，人是有标号的。

显然“每个人至少一件”是非常不好求的，因为这样每种特产之间就不独立了。我们先考虑可以 有人 没有，这样就不会互相影响了。

可以 有人 没有的方案数是非常好求的，设目前有$i$个人，特产用$a$表示，则方案数就是：

这是因为，我们意识到每一种特产之间是相互独立的，考虑第$j$种特产分为$i$份，就相当于把$a_j$个相同元素放到$i$个可空集合的方案数，对应方程$\stackrel{i}{\sum _{k=1}}{x}_k=a_j$的非负整数解的个数。

设$f(i)$表示至多有$i$个人分到至少一份特产的方案数，$g(i)$为恰好有$i$个人分到至少一份的方案数。
则可以反演。

#include<iostream>
using namespace std;
const int N=1000;
const long long M=1e9+7;
long long a[N+5],C[2*N+5][2*N+5],f[N+5],g[N+5];
int n,m;
int main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	for(int i=0;i<=N;i++) C[i][0]=1;
	for(int i=1;i<=2*N;i++)
		for(int j=1;j<=i;j++)
			(C[i][j]=C[i-1][j-1]+C[i-1][j])%=M;
	for(int i=1;i<=n;i++)
		f[i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			(f[i]*=C[a[j]+i-1][i-1])%=M;
//	for(int i=0;i<=n;i++)
//		cout<<i<<':'<<f[i]<<endl;
	for(int i=0;i<=n;i++)
		(g[n]+=C[n][i]*f[i]*((n-i)&1?-1:1))%=M;
	cout<<(g[n]%M+M)%M;		
}

注意到这里g只用到一项，但是为了视觉效果就不改了。

记题目中的k为K。设糖果为a，药片为b。
我们称$a_i>b_j$为合法情况。

首先注意到若n+K为奇数，则无解。（方案数是0）

然后对于K是偶数的情况，注意到题目中有“恰好”这个意思，因此考虑二项式反演。

设$f(i)$表示至少有$i$组a>b的情况数，$g(i)$表示恰好有$i$组a>b的情况数。注意到i是可分的（有i组合法的情况，就会有i-1组合法的情况），并且情况数相同的时候，情况是有不同的，因此可以二项式反演。

接下来求$f(i)$，需要一个简单dp的过程，首先把a、b数组升序排序，然后设$F_{i,j}$表示前i个a，与全部的b做匹配，至少 j组合法情况的方案数。

首先有不知道是合法还是不合法的匹配，$F_{i,j}+=F_{i,j-1}$，合法更好，不合法拉倒。换句话说，搁置$a_i$，$a_i$先不做匹配，等dp到n的位置，确定完了所有合法匹配之后，再做随机匹配。

其次有合法匹配，记b数组中小于$a_i$的有k个，$F_{i,j}+=F_{i-1,j-1}\times (k-(j-1))$。这是因为对于$a_i$而言的合法匹配的区域必然包含原有合法匹配的区域，不能占以前的位置，因此要减去j-1。

考虑边界条件，显然$F_{i,0}=1$，这并不是说有0组合法情况的方案数一定只有一种，而是说当从$F_{i,0}$处转移时，理应获得1的贡献。也可以说我们搁置了$a_1,...,a_i$的所有位置，等到dp到n的时候再随机匹配。

注意到$f(i)=(n-i)!F_{n,i}$，因为有i对合法匹配，剩下的位置被搁置了，随机匹配。

就做完了。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2000;
const long long M=1e9+9;
int n,K;
long long p[N+5],C[N+5][N+5];
long long f[N+5],F[N+5][N+5];
int a[N+5],b[N+5];
int main() {
	cin>>n>>K;
	if((n+K)&1) {
		cout<<0;
		return 0;
	}
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	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])%=M;
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	for(int i=0;i<=n;i++) F[i][0]=1;
//	cout<<"***";
	for(int i=1;i<=n;i++) {
		long long k=upper_bound(b+1,b+1+n,a[i])-b;
//		cout<<k<<' ';
		for(int j=1;j<=i;j++) 
			(F[i][j]+=F[i-1][j]+F[i-1][j-1]*max((long long)k-j,0ll))%=M;
	}
//	for(int i=1;i<=n;i++,cout<<endl)
//		for(int j=1;j<=i;j++)
//			cout<<F[i][j]<<' '; 
//	cout<<"***";
	p[0]=1;
	for(long long i=1;i<=N;i++)
		(p[i]=i*p[i-1])%=M;
	for(int i=0;i<=n;i++)
		(f[i]=F[n][i]*p[n-i])%=M;
	K=n+K>>1;
	long long g=0;
	for(int i=K;i<=n;i++)
		(((g+=C[i][K]*f[i]*(i-K&1?-1:1))%=M)+=M)%=M;
	cout<<g;
}