P7213 [JOISC2020] 最古の遺跡 3

考虑另一种刻画过程的方式：设 \(a_i\) 为原序列，\(b_i\) 为最终序列，则有：

• 从后往前扫描，\(b_i\) 会持续降低到 \([i+1, n]\) 中未出现 \(b_i\)。

考虑 dp，设 \(f(i, j)\) 表示考虑了 \([i, n]\)，当前在 \(b\) 中 \(1 \sim j\) 都出现过的方案数。这里要区分相等的两个数，且只填了 \([1, j]\) 中的数，\([j+1,n]\) 中的数还没分配位置。

若 \(b_i\) 最终降到 \(0\)：

• \(i\) 处可以填 \([1, j]\)，假设 \([i+1,n]\) 中一共有 \(c_0\) 个 \(0\)，则系数为 \(j - c_0\)。

若 \(b_i\) 最终不为 \(0\)：

• 若 \(b_i> j + 1\)，则现在先不分配 \(a_i\)，系数为 \(1\)。
• 若 \(b_i = j + 1\)，枚举此时 \(1 \sim j + k\) 都出现过，则有：
  1. 要在 \([j+1,n]\) 中的非 \(0\) 位置里选出 \(k-1\) 个位置，系数为 \(\dbinom{n-i-c_0}{k-1}\)。
  2. \(a_i\) 可以填 \([j+1, j + k]\)，且 \(j+1\) 有两种选择，系数为 \(k+1\)
  3. 后面 \(k - 1\) 个位置可以填 \([j+2,j+k]\)，且最终要形成 \(j+2 \sim j+k\) 的排列，假设系数为 \(g(k-1)\)。

设有 \(g(n)\) 表示 \(n\) 个位置，\(a_i \in [1, n]\)，且 \(b_i\) 构成 \(1 \sim n\) 的排列的方案数。

转移考虑枚举 \(b_n = i\)，则转化为 \([1, i - 1]\) 和 \([i+1, n]\) 的子问题，有

总时间复杂度 \(\mathrm{O}(n ^ 3)\)。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
using ll = long long;
const int N = 610;
const int M = 1210;
const int MOD = 1e9 + 7;
int n, m, occur[M];
ll fac[M], ifac[M], f[M][N], g[N];
ll Pow(ll a, int p = MOD - 2) {
	ll ans = 1;
	for(; p; p >>= 1, a = a * a % MOD)
		if(p & 1) ans = ans * a % MOD;
	return ans;
}
ll C(int n, int m) {
	if(n < 0 || m < 0 || n < m) return 0;
	return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
int main() {
	//freopen("data.in", "r", stdin);
	//freopen("code.out", "w", stdout);
	cin.tie(0)->sync_with_stdio(0);
	cin >> n, m = n * 2;
	for(int i = 1, x; i <= n; ++i)
		cin >> x, occur[x] = 1;
	fac[0] = 1;
	for(int i = 1; i <= m; ++i)
		fac[i] = fac[i - 1] * i % MOD;
	ifac[m] = Pow(fac[m]);
	for(int i = m - 1; i >= 0; --i)
		ifac[i] = ifac[i + 1] * (i + 1) % MOD;
	g[0] = 1;
	for(int x = 1; x <= n; ++x)
		for(int i = 1; i <= x; ++i)
			g[x] = (g[x] + C(x - 1, i - 1) * (x - i + 2) % MOD * g[i - 1] % MOD * g[x - i]) % MOD;
	f[m + 1][0] = 1;
	int c0 = 0, c1 = 0;
	for(int i = m; i >= 1; --i) {
		for(int j = 0; j <= n; ++j) if(f[i + 1][j]) {
			if(occur[i]) {
				f[i][j] = (f[i][j] + f[i + 1][j]) % MOD;	
				for(int k = 1; k <= n - j; ++k)
					f[i][j + k] = (f[i][j + k] + C(c1 - j, k - 1) * (k + 1) % MOD * f[i + 1][j] % MOD * g[k - 1]) % MOD;				
			}
			else {
				f[i][j] = (f[i][j] + f[i + 1][j] * (j - c0)) % MOD;	
			}
		}
		c0 += occur[i] == 0, c1 += occur[i] == 1;
	}
	printf("%lld\n", f[1][n] * Pow(Pow(2, n)) % MOD);
	return 0;
}