---

以前开过一遍这题，以为很难没刚下去

今天$ review$一遍分析了一下感觉也还好

题意：给定长度为$ n \leq 2000$的数组$ A,B$求完全匹配使得$A>B$的对数比$A<B$的对数恰好多$k$组的方案数

---

$ Solution:$

直接$DP $是$ n^3$的

考虑容斥 先将$ A,B$从小到大排序

设$ F_{i,j}$表示只考虑$ A$的前$ i$个物品，进行了$ j$次匹配均满足$ A>B$的方案数

显然每次$ A$能转移的是$B$的一段前缀区间，且$ i$前面匹配到的$B$一定在当前前缀区间内

有转移式：

$F_{i,j}=F_{i-1,j}+(now_i-j+1)·F_{i-1,j-1}$

其中$ now_i$表示最靠右的比$ A_i$小的$B$数组的位置

令$ g_i=F_{n,i}*(n-i)!$，则$ g_i$表示有至少$ i$对$ A>B$的对数的方案数

令$ f_i$表示有恰好$ i$对$ A>B$的对数的方案数

则根据定义有

$ g_i=\sum\limits_{j=i}^n \binom{j}{i}f_j$

二项式反演得

$ f_i=\sum\limits_{j=i}^n(-1)^{j-i} \binom{j}{i}g_j$

时间复杂度$ O(n^2)$

---

 

$ my \ code$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define p 1000000009#define rt register int#define ll long longusing namespace std;inline ll read(){ ll x = 0; char zf = 1; char ch = getchar(); while (ch != '-' && !isdigit(ch)) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;}void write(ll y){ if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int i,j,k,m,n,x,y,z,cnt;int a[2010],b[2010],inv[2010],g[2010];int main(){ n=read();m=read(); inv[0]=inv[1]=1; for(rt i=2;i<=n;i++)inv[i]=1ll*inv[p%i]*(p-p/i)%p; if(n+m&1)return write(0),0; for(rt i=1;i<=n;i++)a[i]=read(); for(rt i=1;i<=n;i++)b[i]=read(); sort(a+1,a+n+1);sort(b+1,b+n+1); int R=0;g[0]=1; for(rt i=1;i<=n;i++){ while(a[i]>b[R+1]&&R
            
             =1;j--) (g[j]+=1ll*g[j-1]*(R-j+1)%p)%=p; } for(rt i=1,sum=1;i<=n;i++){ sum=1ll*sum*i%p; g[n-i]=1ll*g[n-i]*sum%p; } m=(n+m)/2;int ans=0; for(rt i=m,tag=1,C=1;i<=n;i++,tag*=-1){ (ans+=1ll*g[i]*C*tag%p)%=p; C=1ll*C*(i+1)%p*inv[i-m+1]%p; } cout<<(ans+p)%p; return 0;}