Vexoben
Jul 11, 2018
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3622
（刷新以获取数学公式）
题意
给定长度为n(<=100000)的数组\(a\)，\(b\)，将其两两配对，使\(a_i>b_j\)的对数比\(b_j>a_i\)的对数多\(k\)对，求方案数。
保证\(a,b\)中的数两两不同。
题解
显然只需要\(a_i>b_j\)的对数为\((n+k)/2\)即可。
首先将数组排序。
记\(F_{i,j}\)表示在\(a\)的前\(i\)个数中选出\(j\)个数，在\(b\)中随意选\(j\)个数，且这\(j\)对数全部满足\(a_i>b_j\)的方案数。
记\(t_i\)为\(b\)中小于\(a_i\)的数的个数，那么我们得到转移方程：
\[F_{i,j}=F_{i-1,j}+F_{i-1,j-1}*(t[i]-j+1)\]但\(F\)求出来的显然不是答案。因为我们只考虑到了\(a_i>b_j\)的那些怎么选择与排布，却没管那些\(b_j>a_i\)的配对。
令\(f_i=F_{n,i}\)，\(g_i\)为配对所有的\(n\)个数，恰好有\(i\)对满足了\(a_i>b_j\)
下面考虑将\(f\)与\(g\)相互表示。
将\(f_i\)中没有配对的\(n-i\)个数随意匹配，得到\(f_i*(n-i)!\)种方案。要注意这些随意匹配之后也有可能出现\(a_i>b_j\)的匹配。
考虑\(g\)，对于\(j>=i\)，从\(g_j\)中\(a_i>b_j\)的匹配里任选\(i\)组都会对算入\(f_i*(n-i)!\)的贡献中。
于是我们得到：
\[f_i*(n-i)! = \sum_{j=i}^{n} \dbinom{j}{i}g_j\]这个似乎可以直接反演。暴力点的话\(O(n^2)\)爆算就好了
#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;
}