luoguP4859 已经没有什么好害怕的了

好久没做 luogu 了

还是比较套路

思路

看见“恰好”考虑二项式反演，由于 $n \le 2000$ ，估计要个 $O(n^2)$ 的 dp

设 $m$ 是题目中的 $k$ ，先转化，若 $2 \not \mid n + m$ 显然无解，否则，我们就令 $m = \frac{n + m}{2}$ ，那么问题变为求恰好有 $m$ 对 $a_i > b_i$ 的方案数，记其为 $ans$ ，由二项式反演得 $ans = \sum_{i = m}^n (-1)^{i - m} \binom{i}{m} f_i$ ，其中 $f_i$ 表示钦定必须有 $i$ 个 $a_{x} > b_{x}$ ，其它随便排列的方案数

考虑如何求 $f$ ，把 $a, b$ 排序，记 $f[i, j]$ 为”考虑了前 $i$ 个 $a$ ，已经选出 $j$ 对 $a_x > b_x$ 的方案数”，注意这里只是考虑点了 $j$ 对 $a_x > b_x$ ，其它 $n - j$ 对还没配对，所以其实 $f_i = f[n, i] * (n - i)!$

而 $f[i, j]$ 的转移非常显然，就是考虑是否选第 $i$ 个，我们记 $c[i]$ 表示有多少个 $b$ 小于 $a_i$ ，如果要选 $a_i$ ，那么显然 $b$ 就有 $c[i] - (j - 1)$ 种选择，因为前面 $j - 1$ 个 $a$ 都小于 $a_i$ ，它们配对的 $b$ 都一定会占到 $c[i]$ 中，故有：
$$
f[i, j] = f[i - 1, j - 1] * (c[i] - (j - 1)) + f[i, j - 1]
$$
$O(n^2)$ 转移即可

代码

#include <cstdio>
#include <algorithm>
using LL = long long;
using DB = double;
const int N = 2000 + 100, P = 1e9 + 9;
int n, m, ans = 0;
int f[N], a[N], b[N], c[N], fac[N], ifac[N];
void adj(int &x){ x += (x >> 31) & P; }
int qpow(int x, int y = P - 2)
{
	int res = 1;
	for (; y; y >>= 1, x = LL(x) * x % P) if (y & 1) res = LL(res) * x % P;
	return res;
}
void prev()
{
	fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
	for (int i = 2; i <= n; ++i) fac[i] = LL(i) * fac[i - 1] % P;
	ifac[n] = qpow(fac[n]);
	for (int i = n - 1; i > 1; --i) ifac[i] = LL(i + 1) * ifac[i + 1] % P;
}
int C(int x, int y)
{
	if (x < y) return 0;
	return LL(fac[x]) * ifac[y] % P * ifac[x - y] % P;
}
int main()
{
	scanf("%d %d", &n, &m);
	if ((n + m) & 1) return puts("0"), 0;
	m = (n + m) >> 1;
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	for (int i = 1; i <= n; ++i) scanf("%d", b + i);
	prev();
	std::sort(a + 1, a + n + 1);
	std::sort(b + 1, b + n + 1);
	for (int i = 1, j = 0; i <= n; ++i)
	{
		while (j < n && a[i] > b[j + 1]) ++j;
		c[i] = j;
	}
	f[0] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = std::min(c[i], i); j; --j) adj(f[j] += LL(c[i] - (j - 1)) * f[j - 1] % P - P);
	for (int i = 0; i <= n; ++i) f[i] = LL(f[i]) * fac[n - i] % P;
	for (int i = m; i <= n; ++i)
		if ((i - m) & 1) adj(ans -= LL(f[i]) * C(i, m) % P);
		else adj(ans += LL(f[i]) * C(i, m) % P - P);
	printf("%d\n", ans);
	return  0;
}