$$【组合数学】专题笔记目录$$

把 $a,b$ 合并到 $v$ 数组，并且按照权值降序排序（记得标记元素属于哪一个数组）。
由于 $n \leq 5000$，考虑 DP 解决，设 $f_{i,j}$ 为前 $i$ 个数已经配对了 $j$ 组的和。
由于已经降序排序，所以两个数合并的最小值是后面那个数。
每次往后加一个数，可以选择配对，也可以选择不配对，由此得到转移方程：
$f_{i,j}=f_{i-1,j-1} \times v_i \times (cnt - j + 1) + f_{i-1,j}$

• 注意前面只配对了 $j-1$ 组，所以是乘 $cnt - (j-1) = (cnt - j + 1)$——致敬 zrz。

最终答案即为 $\frac{f_{n * 2, n}}{n!}$

#include <bits/stdc++.h>
using namespace std;
const int N = 5015;
const int mod = 998244353;
int n;
int f[N << 1][N];
pair<int, int> v[N << 1];
int c[2][N << 1];

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first > b.first;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &v[i].first), v[i].second = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &v[i + n].first), v[i + n].second = 1;
    sort(v + 1, v + 1 + 2 * n, cmp);
    for (int i = 1; i <= n * 2; i++) {
        c[0][i] = c[0][i - 1];
        c[1][i] = c[1][i - 1];
        c[v[i].second][i]++;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n * 2; i++) {
        f[i][0] = 1;
        int p = c[v[i].second ^ 1][i];
        for (int j = 1; j <= min(n, i); j++) {
            if (j <= p) f[i][j] = (f[i - 1][j - 1] * 1ll * (p - j + 1) % mod * 1ll * v[i].first) % mod;
            f[i][j] = (f[i][j] * 1ll + f[i - 1][j] * 1ll) % mod;
        }
    }
    int res = 1;
    for (int i = 2; i <= n; i++) res = (res * 1ll * i) % mod;
    printf("%d\n", (f[n * 2][n] * 1ll * qmi(res, mod - 2)) % mod);
    return 0;
}