给定两个数组a[n]与b[n]（数全不相等），两两配对，求“a比b大”的数对比“b比a大”的数对个数多k的配对方案数。
据说做了这题就没什么题好害怕的了，但感觉实际上这是一个套路题，只是很难想到。
首先显然“a比b大”的个数是确定的，问题转化成求“a比b大”的数对个数为m的方案数。
不好算考虑容斥，总结下容斥的一些套路。(From ATP's Blog)
1.全部-至少一个+至少两个-…=一个也没有的
2.所有的-一个也没有的=至少有一个的
3.至少有k个的-C(k+1,k)* 至少有k+1个的+C(k+2,k) *至少有k+2个的…=恰好有k个的
4.将“强制一部分满足要求，一部分不满足”转化为只强制一部分满足要求，然后容斥
5.补集转化 \ Min-Max容斥 \ 与质因子相关的容斥用$\mu$做容斥系数。
（还有一种类似FMT思想的容斥，不过只是用于求解问题中简便使用的，一般不作为容斥方法）
这题用的是第三种，同样的题可见[BZOJ3198][SDOI2013]Spring(容斥+Hash)
这样，问题就变成求“a比b大”的数对个数不少于m的方案数。
将a,b均排序，考虑DP，f[i][j]表示给前i个a中的至少j个安排数值更低的b的方案数。
则有：f[i][j]=f[i-1][j]+f[i-1][j-1]*(k-(j-1))
其中k为b中小于a[i]的最后一个数的位置。
理解起来就是，如果i与k之后的配对，方案数为f[i-1][j]，否则i有k-(j-1)种选法。
问题得解，注意特判n和m不同奇偶，DP转移是特判j=0即可。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std; const int N=;
const ll mod=;
int n,m;
ll ans;
ll f[N][N],C[N][N],fac[N];
int a[N],b[N]; int main(){
freopen("bzoj3622.in","r",stdin);
freopen("bzoj3622.out","w",stdout);
scanf("%d%d",&n,&m);
if ((n^m)&){ puts(""); return ; }
m=(n+m)>>; fac[]=;
rep(i,,n) fac[i]=fac[i-]*i%mod;
rep(i,,n) scanf("%d",&a[i]);
rep(i,,n) scanf("%d",&b[i]);
rep(i,,n){
C[i][]=;
rep(j,,i) C[i][j]=(C[i-][j-]+C[i-][j])%mod;
}
sort(a+,a+n+); sort(b+,b+n+);
f[][]=;
rep(i,,n){
int k=; while (k<=n && b[k]<a[i]) k++; k--;
rep(j,,i) f[i][j]=(f[i-][j]+f[i-][j-]*max(k-j+,))%mod;
f[i][]=f[i-][];
}
ll t=;
rep(i,m,n) f[n][i]=(f[n][i]*fac[n-i])%mod,ans=(ans+t*f[n][i]*C[i][m]%mod+mod)%mod,t=-t;
printf("%lld\n",(ans+mod)%mod);
return ;
}