这题qwq去年五月好像在刷组合计数，然后听说这题挺经典，就看了，结果不会。。咕了好长好长时间之后去看了题解，看着题解中“广义容斥”的式子弄了好久。。还在笔记本（字面意思）上推了。还觉得很牛逼。。

时隔半年多之后，今天裴神犇学了炫酷反演魔术，说可以写“已经没有什么好害怕的了”。我印象里我写过这题，于是重新去看了。不会。

有两个大小为 nn 的序列 AA 和 BB，求排列 {p}\{p\} 的个数满足 Ai>BpiA_i>B_{p_i} 的 ii 的个数恰好为 kk。数据满足 2n2n 个数互不相同。
n≤2000n\leq2000

以下把 Ai>BpiA_i>B_{p_i} 称作满足条件的对。

看起来就很不可做的样子。考虑dp？换了好几个状态都觉得显然没法转移嘛。。
这种暴力是阶乘的题按理说是应该状压比较合理啊？可是这数据范围？
有一个比较看起来正常点的状态是 dp[i][j]dp[i][j] 表示A的前i项恰好j个满足条件的方案数。不过对于一个状态根本不知道选了B中的哪些，没法转移啊。。

于是我们可以考虑换方向了。容斥？好像很靠谱的样子。二项式反演给我们提供了反演的系数：

gi=∑j=in(ji)fj⇔fi=∑j=in(−1)j−i(ji)gjg_i=\sum_{j=i}^n\binom{j}{i}f_j\Leftrightarrow f_i=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}g_j

所以我们现在要求至少有 ii 对满足条件的方案数 gig_i。

然后就是容斥的套路了？既然要求至少，就固定这些，然后其他随便选。

那么换一下状态 dp[i][j]dp[i][j] 表示A的前i项已经固定了j对满足条件的方案数。
也就是说只有满足条件的对才选，不满足条件的先不选。
这样好像就可以转移了耶。我们把A和B都排下序，那么因为能与 Ai−1A_{i-1} 满足条件的 BjB_j 一定可以与 AiA_i 满足条件，所以就可以预处理一波然后dp了。
dp出来之后 gi=dp[n][i]∗(n−i)!g_i=dp[n][i]*(n-i)!，然后直接套式子就出来了。

所以之前觉得很玄乎的“广义容斥”其实就是二项式反演啊。。。

#include<bits/stdc++.h>
using namespace std;
const int N=2020,mod=1e9+9;
int n,k,a[N],b[N],l[N],f[N],J[N],I[N],ans;
int C(int n,int m){return 1ll*J[n]*I[m]%mod*I[n-m]%mod;}
int main(){
    scanf("%d%d",&n,&k);J[0]=I[0]=I[1]=1;
    if((n+k)&1)puts("0"),exit(0);k=(n+k)/2;
    for(int i=2;i<=n;i++)I[i]=mod-1ll*mod/i*I[mod%i]%mod;
    for(int i=1;i<=n;i++)J[i]=1ll*J[i-1]*i%mod,I[i]=1ll*I[i-1]*I[i]%mod;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    sort(a+1,a+n+1);sort(b+1,b+n+1);
    for(int i=1,j=0;i<=n;l[i++]=j)
        while(j<n&&a[i]>b[j+1])j++;
    f[0]=1;
    for(int i=1;i<=n;i++)for(int j=l[i];j;j--)
        f[j]=(f[j]+1ll*f[j-1]*(l[i]-j+1))%mod;
    for(int i=1;i<=n;i++)f[i]=1ll*f[i]*J[n-i]%mod;
    for(int i=k;i<=n;i++)(k-i)&1?ans=(ans-1ll*C(i,k)*f[i])%mod:ans=(ans+1ll*C(i,k)*f[i])%mod;
    printf("%d\n",(ans+mod)%mod);
    return 0;
}