这题很有意思阿。
首先把 \(A, B\) 放一起从大到小排序得到序列 \(C\)，原先在 \(A\) 的点染红色否则染蓝色，就变成了以任意顺序匹配 \(n\) 对红蓝点，且权值为后面出现的点。
设 \(f_{i, j}\) 表示前 \(i\) 个点匹配了 \(j\) 对，则有方程：
\[f_{i, j} = f_{i - 1, j - 1} \times C_i \times (tmp - (j - 1)) + f_{i - 1, j}
\]
其中 \(tmp\) 是当前与 \(i\) 颜色不同的点个数。
时间复杂度 \(\mathcal{O}(n^2)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 5e3 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n, a[N], b[N], f[N], g[N], s[2][N << 1];
pii c[N << 1];
int qpow(int a, int b) {int res = 1;for (; b; b >>= 1, a = (ll)a * a % mod) if (b & 1) res = (ll)res * a % mod;return res;
}
void main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i], c[i] = {a[i], 0};for (int i = 1; i <= n; i++) cin >> b[i], c[i + n] = {b[i], 1};int m = n << 1;sort(c + 1, c + m + 1, greater<pii>());f[0] = 1;for (int i = 1; i <= m; i++) {memset(g, 0, sizeof g);s[0][i] = s[0][i - 1]; s[1][i] = s[1][i - 1];s[c[i].second][i]++;int tmp = s[!c[i].second][i];for (int j = 0; j <= min(n, i); j++) {g[j] = f[j];if (j <= tmp) g[j] = (g[j] + (ll)f[j - 1] * c[i].first % mod * (tmp - j + 1) % mod) % mod;}memcpy(f, g, sizeof f);}int ans = f[n], fac = 1;for (int i = 1; i <= n; i++) fac = (ll)fac * i % mod;cout << (ll)ans * qpow(fac, mod - 2) % mod << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}
这题还是很好的，下面总结一下：
- 有关 min/max 的 DP 可以考虑排序。
- 排列计数有时可以转化为匹配问题。