Description：

给 $2$ 组每组 $n$ 个互不相同的数，求有多少种两两配对的方案使得第一组中的数 $>$ 第二组中的数的对数恰好为 $k$ 。

$1\leqslant n\leqslant 2000$

Solution：

容斥 $+DP$ 的套路，然而不会 $DP$ 。

题目含义可以转化为选出 $\frac{n+k}2$ 组。

正解是先把两组排序，预处理一个 $cnt[i]$ 表示 $b[]$ 中有几个数小于 $a[i]$ ，设 $f[i][j]$ 表示前 $i$ 个数至少选出 $j$ 对上述情况的方案数，转移方程为 $f[i][j]=f[i-1][j]+f[i-1][j-1]\times \max(cnt[i]-(j-1),0)$ 。最后容斥一下就行了，容斥系数就是组合数。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 2010

int a[MAXN],b[MAXN];

int f[MAXN][MAXN];

int cnt[MAXN];

int g[MAXN];

int fac[MAXN];

int C[MAXN][MAXN];

#define MOD 1000000009

int main()

{

	scanf("%d%d",&n,&k);

	k = (n + k) / 2;

	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 + 1 + n);

	sort(b + 1,b + 1 + n);

	for(int i = 1,j = 0;i <= n;++i)

	{

		while(j < n && b[j + 1] < a[i])++j;

		cnt[i] = j;

	}

	for(int i = 0;i <= n;++i)f[i][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			f[i][j] = (f[i - 1][j] + 1ll * f[i - 1][j - 1] * max(0,cnt[i] - (j - 1)) % MOD) % MOD;

		}

	}

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	for(int i = 1;i <= n;++i)g[i] = 1ll * f[n][i] * fac[n - i] % MOD;

	C[0][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		C[i][0] = C[i][i] = 1;

		for(int j = 1;j < i;++j)

		{

			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;

		}

	}

	int ans = g[k];

	for(int i = k + 1;i <= n;++i)

	{

		ans = (ans + 1ll * (((i - k) & 1) ? -1 : 1) * C[i][k] * g[i] % MOD + MOD) % MOD;

	}

	cout << ans << endl;

	return 0;

}