洛谷 P4859 已经没有什么好害怕的了 题解（DP，二项式反演）

给两个长为 \(n\) 的数组 \(a, b,\) 求将 \(a_i, b_j\) 两两匹配使得 \(a_i > b_j\) 的数量比 \(a_i < b_j\) 的数量多 \(k\)。数字不重复, \(k \le n \le 2000\)。

注意到，其实 \(a_i>b_j\) 和 \(a_i<b_j\) 分别的个数都是确定的，其中需要有 \(\frac{n+k}{2}\) 个 \(a_i>b_j\)，\(\frac{n-k}{2}\) 个 \(a_i<b_j\)。于是问题就被转化成，有多少种将 \(a_i,b_j\) 两两配对的方案，使得 \(a_i>b_j\) 的个数恰好为 \(\frac{n+k}{2}\)。如果 \(n+k\) 是奇数那么无解。下文为了表述方便，令 \(k=\frac{n+k}{2}\)。

然后我们发现出现了“恰好”的限制，“恰好”的限制一般来讲是不好计数的。遇到这种问题，我们可以先求出“至少”的方案数，然后再通过二项式反演推出恰好的方案数。

首先我们将 \(a_i,b_i\) 都从小到大排序，这样对于每一个 \(a_i\) 来说，他能匹配的 \(b_j\) 恰好就是一段前缀，且这个前缀的长度只增不减。接下来，考虑设 \(f_{i,j}\) 表示考虑了 \(a\) 的前 \(i\) 个数，其中我们钦定匹配了 \(j\) 对（这里的钦定就是恰好的意思，剩下的 \(a_i\) 是否匹配我们不管）的匹配方案数。注意这里状态不是所有的数的匹配方案数，而是指的是我们钦定的那些数的匹配方案数。因为如果我们把状态设为了前者，转移就不太方便了。

然后现在我们考虑怎么做转移。如果 \(a_i\) 我们要钦定他和一个 \(b\) 去匹配，那么一共有 \(cnt_i-j\) 种方案，其中 \(cnt_i\) 是比 \(a_i\) 小的 \(b\) 的数量。如果 \(a_i\) 不与任意一个 \(b\) 去匹配，那么方案数就不变。于是有：

\[f_{i,j}\gets f_{i-1,j-1}\times (cnt_i - (j-1)) + f_{i-1,j} \]

当我们算完之后，再统一算剩下的没有钦定的数的贡献：

\[f_{n,k}\gets f_{n,k}\times (n-k)! \]

现在我们有了【至少选 \(k\) 个 \(a_i>b_j\) 的方案数 \(f_{n,k}\)】，我们想要推回恰好选 \(k\) 个的方案数 \(ans_k\)，因为有：

\[f_{n,k}=\sum_{i=k}^n\binom{i}{k}ans_i \]

利用二项式反演，我们就能求出 \(ans_i\) 了：

\[ans_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_{n,i} \]

const int MAXN = 2e3 + 5, mod = 1e9 + 9;
int n, k, f[MAXN][MAXN], cnt[MAXN], a[MAXN], b[MAXN], fac[MAXN], ifac[MAXN];void add(int &x, int y) {x += y;if (x >= mod) x -= mod;
}int quickpow(int a, int b) {int ret = 1;while (b) {if (b & 1) ret = ret * a % mod;a = a * a % mod; b >>= 1;}return ret;
}int C(int n, int m) {if (n < m) return 0;return fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}void work() {cin >> n >> k;for (int i = 1; i <= n; ++i)cin >> a[i];for (int i = 1; i <= n; ++i)cin >> b[i];sort(a + 1, a + 1 + n);sort(b + 1, b + 1 + n);if ((n + k) % 2 == 1) return cout << 0 << endl, void();k = (n + k) / 2;int j = 0;for (int i = 1; i <= n; ++i) {while (j < n && b[j + 1] < a[i]) ++j;cnt[i] = j;}f[0][0] = 1;for (int i = 1; i <= n; ++i) {for (int j = 0; j <= n; ++j) {f[i][j] = f[i - 1][j];if (j > 0 && j <= cnt[i]) add(f[i][j], f[i - 1][j - 1] * (cnt[i] - (j - 1)) % mod);}}fac[0] = 1;for (int i = 1; i <= n; ++i)fac[i] = fac[i - 1] * i % mod;ifac[n] = quickpow(fac[n], mod - 2);for (int i = n - 1; i >= 0; --i)ifac[i] = (ifac[i + 1] * (i + 1)) % mod;for (int i = 0; i <= n; ++i)f[n][i] = f[n][i] * fac[n - i] % mod;int ans = 0, coff = 1;for (int i = k; i <= n; ++i) {add(ans, coff * C(i, k) % mod * f[n][i] % mod);coff = (mod - coff);}cout << ans << endl;
}