题目概述

有 $n$ 个带权糖果和 $n$ 个带权药片，求一一配对后糖果权值大于药片权值比药片权值大于糖果权值对数多 $K$ 的方案数。

解题报告

emm……我刚开始想的是求出 $\ge K$ 的方案数然后容斥来着，很不可做……实际上设 $A$ 为糖果大于药片，$B$ 为药片大于糖果，由于 $A+B=n,A=B+K$ 所以 $A={n+K\over2},B={n-K\over 2}$ 是已知的啊QAQ。

那么就不用管 $B$ 了，我们只要求出糖果大于药片的对数 $\ge A$ 的方案数就行了，这个可以通过先强制选出 $A$ 对糖果大于药片然后剩下的乱配对来求出。

考虑DP：$f_{i,j}$ 表示前 $i$ 个糖果匹配（糖果权值大于药片权值）了 $j$ 个的方案数，发现这样是假的，因为无法确定药片被匹配了的状态……不难想到糖果和药片都排序一下，这样大的糖果选的区间就包括了小的糖果选的区间，也就是说在 $f_{i,j}$ 状态时 $i$ 能匹配的已经用掉了 $j$ 个，令 $num_i$ 表示 $i$ 能匹配的数量，得到转移方程：

$$ f_{i,j}=f_{i,j-1}+(num_i-j+1)f_{i-1,j-1} $$

然后运用广义容斥（证明可以看这篇，应该是差不多的）将 $\ge A$ 转化为 $=A$ ，答案就是：

$$ \sum_{i=A}^{n}(-1)^{i-A}{i\choose A}f_{n,i}(n-i)! $$

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=2000,MOD=1e9+9;

int n,K,a[maxn+5],b[maxn+5],num[maxn+5],f[maxn+5][maxn+5],fac[maxn+5],INV[maxn+5],ans;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i]*INV[i-1]%MOD;
}
#define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);if (n-K&1) return puts("0"),0;K=n+K>>1;Make(n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n);
    for (int i=1;i<=n;i++) scanf("%d",&b[i]);sort(b+1,b+1+n);
    for (int i=1,j=1;i<=n;num[i++]=j-1) while (j<=n&&a[i]>b[j]) j++;
    for (int i=f[0][0]=1;i<=n;i++)
        for (int j=0;j<=i;j++)
            {f[i][j]=f[i-1][j];if (j&&num[i]>=j) AMOD(f[i][j],(LL)f[i-1][j-1]*(num[i]-j+1)%MOD);}
    for (int i=1;i<=n;i++) f[n][i]=(LL)f[n][i]*fac[n-i]%MOD;
    for (int i=K;i<=n;i++) {int now=i-K&1?MOD-1:1;now=(LL)now*C(i,K)%MOD*f[n][i]%MOD;AMOD(ans,now);}
    return printf("%d\n",ans),0;
}