LOJ3276 「JOISC 2020 Day2」遗迹

题意：给定一个长度为 $2n$ 的序列，其中 $[1, n]$ 各出现 2 次，对序列一直操作直到不再变化：从前向后操作每一个数，如果这个数不为 0 并且在其后面存在一个和其相等的数，则将这个数减 1。可以证明最后存在 $n$ 个数不为 0。先给出这 $n$ 个位置，求有多少个序列满足操作后剩这些位置。$n\leq 600$。

这个的性质并不是很优美，我们考虑直接暴力 DP。

把这个序列 reverse 一下。

记 $f(i, j)$ 表示处理了前 $i$ 个，且前面 $[1, j]$ 在操作后已经存在的方案数（暗示 $j + 1$ 操作后不会存在）。注意到我们无法对 $[j + 2, n]$ 的出现情况压进状态，所以我们考虑如果出现了 $[j + 2, n]$ 的数，我们先视而不见，后面需要用到的时候再将其加入，因为他还用不到。

考虑转移，如果这一位最后剩的 0，那么这个数开始必须是 $[1, j]$。考虑计算 $[1, j]$ 中有多少个。注意一个问题是我们现在不好区分这个是第一还是第二，那么我们考虑对于所有相同的数假设不相同，最后再除以阶乘。假设前面有 $c$ 个位置最后不剩 0（包含 $i$），那么所有 $2j$ 个数已经被占领了 $i - 1 - c$，剩下的就都可以选择。

如果最后剩的 1，那么考虑两个情况：

1. 这个数最后剩的不是 $j + 1$。按照前面的理论，我们先不计算他的贡献。
2. 最后剩的是 $j + 1$。假设现在变成了 $[1, j + k]$，那么 $[j + 2, j + k]$ 的所有数都需要在前面完成，并且 $i$ 位置最后必须剩 $j + 1$。注意到我们需要从剩下的 $c - j - 1$ 个数中选取 $k - 1$ 个数，并且让他最后覆盖 $[j + 2, j + k]$。容易发现这个式子只与 $k - 1$ 有关，假设为 $add_{k - 1, k - 1}$。剩下的 $i$ 位置，只能填 $[j + 1, k]$ 的数，我们可以从剩下的 $2k - (k - 1) = k + 1$ 个数中选择。于是可以得到转移方程为：

$$dp_{i - 1, j}\times \binom{c - j - 1}{k - 1} add_{k - 1, k - 1}(k + 1) \to dp_{i, j + k}$$

最后一个问题就是如何计算 $add_{k, k}$。首先发现这个等价于计算 $k$ 个数，任意满足 $\in [i, k]$ 的数都 $\geq k - i + 1$，也就是满足 $[1, i]$ 的数都 $\leq i$。注意到一个数只能选择两次，考虑直接 DP。$add_{i, j}(j\leq i)$ 表示选择了 $[1, i]$ 的数，并且选了 $j$ 个的序列数。枚举 $i$ 是选择了 0、1、2 个容易得到转移方程：

$$add_{i, j} = add_{i - 1, j} + 2j\times add_{i - 1, j - 1} + j(j - 1)\times add_{i - 1, j - 2}$$

该部分复杂度 $O(n ^ 2)$。

主 DP 复杂度 $O(n ^ 3)$，总复杂度即为 $O(n ^ 3)$。注意我们开始把任意两个相同的数当作不同了，于是需要除以 $2 ^ n$。

int main()
{
	init();
	std::cin >> n;
	int x, cnt = 0;
	for (int i = 1; i <= n; ++ i) scanf("%d", &x), key[2 * n - x + 1] = true;
	add[0][0] = 1;
	for (int i = 1; i <= n; ++ i)
		for (int j = add[i][0] = 1; j <= i; ++ j) {
			add[i][j] = (add[i - 1][j] + add[i - 1][j - 1] * 2LL * j) % Mod;
			if (j > 1) add[i][j] = (add[i][j] + add[i - 1][j - 2] * (j - 1LL) * j) % Mod;
		}
	f[0][0] = 1;
	for (int i = 1; i <= 2 * n; ++ i)
		if (key[i]) {
			++ cnt;
			for (int j = 0; j < cnt; ++ j) if (f[i - 1][j])
				for (int nxt = 1; nxt + j <= cnt; ++ nxt)
					f[i][j + nxt] = (f[i][j + nxt] + (LL) f[i - 1][j] * C[cnt - j - 1][nxt - 1] % Mod
						* add[nxt - 1][nxt - 1] % Mod * (nxt + 1)) % Mod;
			for (int j = 0; j < cnt; ++ j)
				adj(f[i][j] += f[i - 1][j] - Mod);
		} else {
			for (int j = 0; j <= cnt; ++ j)
				f[i][j] = (LL) f[i - 1][j] * (j - (i - 1 - cnt)) % Mod;
		}
	std::cout << (LL) f[2 * n][n] * qpow(2, Mod - 1 - n) % Mod << '\n';
	return 0;
}