洛谷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;
}