考虑对于给定的起始如何求最终状态。
按编号从大到小依次考虑每一根石柱，设 \(\mathrm{used}_i\) 表示目前是否有石柱的最终高度为 \(i\)。
则第 \(i\) 根石柱的最终高度为 \(\max\limits_{1 \le j \le h_i,\neg\mathrm{used}_j} j\)。
考虑模拟这个过程进行 DP。
设 \(f_{i,j}\) 表示 \([i,2N]\) 的最终高度中已知出现了 \([1,j]\) 中的每一个整数，且 \(j\) 是极大的。
考虑从 \(f_{i+1}\) 转移到 \(f_i\)：
- 若 \(i \not \in A\)： 则显然有 \(1 \le h_i \le j\)，否则便可以取到 \(j+1\) 作为最终状态。
然而并不清楚 \([1,j]\) 中还有哪些可以用，因为难以得知使用的次数。
此时考虑将问题转化为同一种高度的石柱之间有区别。
则可以取的值有 \(j - \mathrm{in}\)，其中 \(\mathrm{in} = \sum\limits_{j=i}^{2N} [j \in A]\)。 - 若 \(i \in A\)： 则假定 \(i\) 的最终状态为 \(j+1\)；若不是，也会存在另一个状态统计到其贡献。
考虑枚举 \(k\) 表示确定了 \(h_i\) 之后使极长前缀达到了 \([1,j+k]\)。
那么显然可以使用的高度有 \(\mathrm{in}-j\) 种，要在其中选 \(k-1\) 种。
接着需要求出将这 \(k-1\) 个位置的最终状态恰好填为 \([j+2,j+k]\) 的方案数。需要注意的是，这些位置的初始高度仅能使用 \([j+2,j+k]\) 内的值。
注意到这可以表示为 \(\mathrm{coe}_{k-1}\)，等会再讨论。
最后，\(h_i\) 能取到的值，有 \(j+1\) 处的两个，和 \([j+2,j+k]\) 剩下的 \(k-1\) 个，共 \(k+1\) 个。
接下来考虑 \(\mathrm{coe}_k\)。
注意到一个方案合法，当且仅当对于任意 \(1 \le i \le k\) 都满足不超过 \(i\) 的元素个数不超过 \(i\)（套娃警告）。
那么便可以借助这个性质，设 \(g_{i,j}\) 表示在 \(j\) 个位置中填不超过 \(i\) 的元素，且满足上述条件的方案数。
分别考虑用 \(0,1,2\) 个 \(i\)，可得 \[
g_{i,j} = g_{i-1,j} + g_{i-1,j-1} \cdot 2j + g_{i-1,j-2} \cdot j(j-1)
\]
又有 \(\mathrm{coe}_k = g_{k,k}\)。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
const int N = 1200;
const int mod = 1e9 + 7;
const int inv = 5e8 + 4;
int n,vis[N + 5];
int f[N + 5][N + 5],c[N + 5][N + 5],coe[N + 5][N + 5];
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int main()
{
scanf("%d",&n),f[(n << 1) | 1][0] = 1;
for(register int i = 0;i <= n;++i)
{
c[i][0] = coe[i][0] = 1;
for(register int j = 1;j <= i;++j)
c[i][j] = add(c[i - 1][j - 1],c[i - 1][j]),
coe[i][j] = (coe[i - 1][j] + 2LL * j * coe[i - 1][j - 1]) % mod,
j >= 2 && (coe[i][j] = (coe[i][j] + (long long)coe[i - 1][j - 2] * j * (j - 1)) % mod);
}
int x;
for(register int i = 1;i <= n;++i)
scanf("%d",&x),vis[x] = 1;
for(register int i = n << 1,in = 0;i;in += vis[i--])
if(vis[i])
for(register int j = 0;j <= in;++j)
{
f[i][j] = add(f[i][j],f[i + 1][j]);
for(register int k = 1;j + k <= in + 1;++k)
f[i][j + k] = (f[i][j + k] + (long long)c[in - j][k - 1] * coe[k - 1][k - 1] % mod * (k + 1) % mod * f[i + 1][j]) % mod;
}
else
for(register int j = 0;j <= in;++j)
f[i][j] = (long long)f[i + 1][j] * (j - (n << 1) + i + in) % mod;
printf("%lld\n",(long long)f[1][n] * fpow(inv,n) % mod);
}