MX galaxy Day16

match

\(B\) 中的每个元素有两种选择，匹配一个点，或者 \([1, a_i]\) 中的每个点都强制被匹配。
容易想出 \(O(n^3)\) 的 \(DP\) 。（真简单吗？我考场想了两个小时）
记 \(dp[i, j, k]\) 表示考虑了前 \(i\) 个，匹配了 \(j\) 个，还剩下 \(k\) 个强制匹配的点没有匹配。

我们发现强制匹配的限制只有最大的那个有用，枚举最大的限制 \(i\) 。
强制第 \(i\) 个不匹配，所有的 \(j>i\) 都选择匹配。
那么 \(A\) 中前 \(a_i\) 个必须匹配，再枚举一个 \(k\) , 表示 \(1\sim i-1\) 中匹配了几个点。
发现这些匹配一定是在前 \(a_i\) 个中的。

对于剩下的 \(a_i-k\) 个点，需要与 \(j>i\) 的元素匹配。
但这样是与 \(i\) 有关的。很难转移。
考虑剩下的元素。
因为所有的 \(j>i\) 都必须匹配，其中 \(a_i-k\) 个点与 \(1\sim a_i\) 匹配了。
剩下的 \(n-i-a_i+k\) 个点就只能与 \(a_i + 1\sim n\) 匹配。
发现是一个对称的子问题。

然后我们就可以枚举分界点把两份 \(DP\) 的结果拼起来了。
具体的，设 \(f[i, j]\) 表示 \(B\) 中 \(i\) 这个前缀匹配了 \(j\) 个点的方案数， \(g[i, j]\) 表示 \(A\) 中 \(i\) 这个后缀匹配了 \(j\) 个点的方案数。
枚举分界点 \(i\) 以及 \(j<i\) 中匹配了 \(k\) 个点。
贡献 \(f[i-1, k]\times g[a_i+1, n-i-a_i+k]\times (a_i-k)!\) 。

（阶乘是因为 \(j>i\) 向前匹配是任意的）

点击查看代码

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)const int _ = 3000 + 7;
const int mod = 1e9 + 7;
typedef long long ll;int n, a[_], b[_], f[_][_], g[_][_], ans, fac[_];void Add(int& x, int y) { x = (x + y > mod) ? x + y - mod : x + y; }int main() { fac[0] = 1;scanf("%d", & n);lep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % mod;lep(i, 1, n) scanf("%d", a + i), ++b[a[i]];rep(i, n - 1, 1) b[i] += b[i + 1];std::sort(a + 1, a + 1 + n);f[0][0] = 1;lep(i, 0, n - 1) lep(j, 0, a[i]) {Add(f[i + 1][j], f[i][j]);if (a[i + 1] - j > 0) Add(f[i + 1][j + 1], 1ll * f[i][j] * (a[i + 1] - j) % mod);}g[n + 1][0] = 1;rep(i, n + 1, 2) lep(j, 0, b[i]) {Add(g[i - 1][j], g[i][j]);if (b[i - 1] - j > 0) Add(g[i - 1][j + 1], 1ll * g[i][j] * (b[i - 1] - j) % mod);}lep(i, 1, n) lep(k, 0, a[i]) Add(ans, 1ll * f[i - 1][k] * g[a[i] + 1][n - i - a[i] + k] % mod * fac[a[i] - k] % mod);printf("%d\n", ans);return 0;
}