洛谷P4859 已经没有什么好害怕的了题解

题意：

已经使 Madoka 有签订契约，和自己一起战斗的想法后，Mami 忽然感到自己不再是孤单一人了呢。

于是，之前的谨慎的战斗作风也消失了，在对 Charlotte 的傀儡使用终曲——Tiro Finale 后，Mami 面临着即将被 Charlotte 的本体吃掉的局面。

这时，已经多次面对过 Charlotte 的 Homura 告诉了学 OI 的你这样一个性质：Charlotte 的结界中有两种具有能量的元素，一种是“糖果”，另一种是“药片”，各有 $n$ 个。在 Charlotte 发动进攻前，“糖果”和“药片”会两两配对，若恰好糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多 $k$ 组，则在这种局面下，Charlotte 的攻击会丟失，从而 Mami 仍有消灭 Charlotte 的可能。

你必须根据 Homura 告诉你的“糖果”和“药片”的能量的信息迅速告诉 Homura 这种情况的个数。

省流：

给出两个长度均为 $n$ 的序列 $a$ 和 $b$ ，保证这 $2n$ 个数互不相同。

现要将 $a$ 序列中的数与 $b$ 序列中的数两两配对

求「 $a_i>b_j$ 的对数比 $a_i<b_j$ 的对数恰好多 $k$ 对」的配对方案数模 $10^9+9$。

输入格式：

第一行两个整数 $n,k$，含义如题目所描述。

接下来一行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个糖果的能量。

接下来 $n$ 个整数，第 $j$ 个数表示第 $j$ 个药片的能量。

保证上面两行不会有重复的数字。

输出格式：

一个答案，表示消灭 Charlotte 的情况个数，需要对 $10^9+9$ 取模。

数据范围：

对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le k \le n$。

显然 $n,k$ 奇偶性不同时必然无解；否则 $A>B$ 的对数恰好为 $m = \frac{n + k}{2}$ 对。

由于「恰好 $m$ 对」这个东西不太好算，考虑「钦定 $m$ 对」然后利用二项式反演计算

首先将 $a,b$ 升序排序，设 $\mathrm{dp}(i,j)$ 表示考虑了 $a$ 的前 $i$ 个数，钦定了 $j$ 对 $a>b$ 的方案数。

转移考虑 $A_i$ 的配对情况：

若不配对，则方案数为 $\mathrm{dp}(i-1,j)$
若配对，即 $b$ 中有 $p_i$ 个数比 $a_i$ 小，则方案数为 $\mathrm{dp}(i-1,j-1)\times (p_i - (j - 1))$

那么

$\mathrm{dp}(i,j) = \mathrm{dp}(i-1,j) + \mathrm{dp}(i-1,j-1)\times(p_i - j + 1)$

设 $f_i$ 为钦定有 $i$ 对 $A>B$ 的方案数，并设 $g_i$ 为恰好有 $i$ 对 $A>B$ 的方案数。那么

$\begin{aligned} f_m &= (n-m)!\times \mathrm{dp}(n,m) \\[6pt]&= \sum_{i=m}^n\binom{i}{m}g_i \end{aligned}$

提示：这里钦定 $i$ 对的意思是我们想计算 $i$ 对的情况，但是当前的式子可能会把多于 $i$ 对的情况算进去。

根据二项式反演有

$\begin{aligned} g_m &=\sum_{i=m}^n(-1)^{i-m}\binom{i}{m} f_i \\[6pt] &=\sum_{i=m}^n(-1)^{i-m}\binom{i}{m}(n-i)!\times \mathrm{dp}(n, i) \end{aligned}$

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 9;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2333))

int fac[N], a[N], b[N], C[N][N], dp[N][N];
void init(int n)
{
    fac[0] = 1; rep(i, 0, n) C[i][0] = 1;
    rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    rep(i, 1, n) rep(j, 1, i) add(C[i][j] = C[i - 1][j - 1], C[i - 1][j]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, k, res = 0; cin >> n >> k;
    if((n ^ k) & 1) return cout << "0\n", 0;
    k = (n + k) / 2; init(n);
    rep(i, 1, n) { cin >> a[i]; } sort(a + 1, a + 1 + n); 
    rep(i, 1, n) { cin >> b[i]; } sort(b + 1, b + 1 + n);
    rep(i, 0, n) dp[i][0] = 1;
    rep(i, 1, n)
    {
        static int p = 0; while(p < n && b[p + 1] < a[i]) ++p;
        rep(j, 1, n) add(dp[i][j] = dp[i - 1][j], dp[i - 1][j - 1] * (p - j + 1) % mod);
    }
    rep(i, k, n)
    {
        if((i - k) & 1) add(res, mod - C[i][k] * dp[n][i] % mod * fac[n - i] % mod);
        else add(res, C[i][k] * dp[n][i] % mod * fac[n - i] % mod);
    }
    cout << res << '\n';
    return 0;
}