Vexoben
Jul 11, 2018
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3622
（刷新以获取数学公式）
题意
给定长度为n(<=100000)的数组，，将其两两配对，使的对数比的对数多对，求方案数。
保证中的数两两不同。
题解
显然只需要的对数为即可。
首先将数组排序。
记表示在的前个数中选出个数，在中随意选个数，且这对数全部满足的方案数。
记为中小于的数的个数，那么我们得到转移方程：
但求出来的显然不是答案。因为我们只考虑到了的那些怎么选择与排布，却没管那些的配对。
令，为配对所有的个数，恰好有对满足了
下面考虑将与相互表示。
将中没有配对的个数随意匹配，得到种方案。要注意这些随意匹配之后也有可能出现的匹配。
考虑，对于，从中的匹配里任选组都会对算入的贡献中。
于是我们得到：
这个似乎可以直接反演。暴力点的话爆算就好了
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
const int mod=1e9+9;
int n,k,a[N],b[N],fac[N];
int f[N],g[N],fx[N][N],c[N][N];
int main() {
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
if ((n+k)%2==1) return 0*puts("0");
sort(a+1,a+n+1); sort(b+1,b+n+1);
for (int i=1;i<=n;i++) a[i]=upper_bound(b+1,b+n+1,a[i])-b-1;
fac[0]=1;
for (int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
for (int i=0;i<=n;i++) {
for (int j=0;j<=i;j++) {
if (j==0) c[i][j]=1;
else c[i][j]=c[i-1][j]+c[i-1][j-1];
if (c[i][j]>=mod) c[i][j]-=mod;
}
}
fx[0][0]=1;
for (int i=1;i<=n;i++) {
for (int j=0;j<=i;j++) {
fx[i][j]=fx[i-1][j];
if (j>0) fx[i][j]+=1LL*fx[i-1][j-1]*(a[i]-j+1)%mod;
if (fx[i][j]>=mod) fx[i][j]-=mod;
}
}
for (int i=0;i<=n;i++) f[i]=fx[n][i];
for (int i=n;i>=1;i--) {
g[i]=1LL*f[i]*fac[n-i]%mod;
for (int j=i+1;j<=n;j++) {
g[i]=(g[i]-1LL*c[j][i]*g[j])%mod;
if (g[i]<0) g[i]+=mod;
}
}
printf("%d\n",g[(n+k)/2]);
return 0;
}