[JOISC2020] 最古の遺跡 3
好难的题。
首先考虑给出 \(h\) 怎么求 \(A\) ，设 \(h'_i\) 为 \(i\) 位置剩下的高度，没了就 \(=0\)。
方便起见，我们把原序列翻转一下，那么题目的操作就是，每种高度的最靠左的位置不变。
我们从左到右依次求解，先令 \(h'_i=h_i\)，若 \(h'_i\) 在 \(j<i\) 的 \(h'_j\) 中出现过，那么 \(h'_i\) 一定会被震低，让 \(h'_i-1\) 继续判断即可。直到没出现过或者 \(h'_i=0\) 。
设 \(H\) 为最大的，满足 \(1\to H\) 的高度在前 \(i-1\) 的 \(h'\) 中都出现的 \(H\) ，那么 \(i\) 位置被保留当且仅当 \(H< h_i\) 。
设 \(dp_{i,j}\) 为考虑到了第 \(i\) 个位置， \(H=j\) 的方案数。
-
若 \(i\notin A\)，则 \(h_i\leq H\)，\(h_i\) 一共有 \(H-c_0\) 种取法，其中 \(c_0\) 为 \(j\notin A,j<i\) 的 \(j\) 个数，注意此求法相当于给同一种高度的两个数加以区分了，所以最后要除以 \(2^n\) 。
-
若 \(i\in A\)，则 \(h_i>H\) ，但是 \(h_i\) 不一定会影响到 \(H\)，这是不好算的，我们考虑在 \(H\) 改变时一起计算，因此：
-
- 加入该位置不改变 \(H\)，我们把该位置的贡献延后计算。
-
- 加入该位置改变了 \(H\)，容易发现此时一共有 \(c_1-H\) 个位置被延后计算了，其中 \(c_1\) 为 \(j\in A,j<i\) 的 \(j\) 个数。那么我们枚举新的 \(H=k\)，那么因为 \(i\) 是第一个改变了 \(H\) 的位置，所以 \(h'_i=j+1\)，那么 \(h_i\) 的取值一共有 \((k-j-1)+2\)，其中 \(k-j-1\) 是因为这些数在被延后计算的数占用过了，\(+2\) 是因为 \(j+1\) 必定没有被用过。然后还要选出剩下的 \(k-j-1\) 个被延后计算的位置，那就是 \(\binom{c_1-j}{k-j-1}\)，最后还要进行给这 \(k-j-1\) 个数填数，也就是：用 \(j+2\to k\) 这些数字给 \(k-j-1\) 个位置填数，满足他们的 \(h'\) 恰好构成 \(j+2\to k\) 的方案数，我们记为 \(g_{k-j-1}\) 。
\(g_n\) 的求法，显然充要条件是对于任意 \(1\leq i\leq n\)，最多有 \(i\) 个位置填的数 \(\leq i\) ，那么我们记 \(t_{i,j}\) 表示填到 \(i\)，填了 \(j\) 个位置的方案数，转移是简单的。
复杂度 \(O(n^3)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 1202;
const int mod = 1e9+7;
int n;
bool key[N];
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
int binom[N][N],g[N],t[N][N];
int dp[N][N];
const int inv2=(mod+1)/2;
int main()
{
read(n);
int m=n*2;
for(int i=1;i<=n;i++)
{
int x;
read(x);
x=m-x+1;
key[x]=1;
}
binom[0][0]=1;
for(int i=1;i<=m;i++)
{
binom[i][0]=1;
for(int j=1;j<=i;j++)
binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%mod;
}
g[0]=1;
for(int L=1;L<=n;L++)
{
for(int i=0;i<=L;i++)
for(int j=0;j<=L;j++)
t[i][j]=0;
t[0][0]=1;
for(int i=1;i<=L;i++)
for(int j=0;j<=i-1;j++)
if(t[i-1][j])
{
t[i][j]=(t[i][j]+t[i-1][j])%mod;
t[i][j+1]=(t[i][j+1]+2ll*(L-j)*t[i-1][j]%mod)%mod;
t[i][j+2]=(t[i][j+2]+1ll*(L-j)*(L-j-1)%mod*t[i-1][j]%mod)%mod;
}
g[L]=t[L][L];
}
dp[0][0]=1;
int c0=0,c1=0;
for(int i=1;i<=m;i++)
{
if(!key[i])
{
for(int j=0;j<=n;j++)
if(dp[i-1][j])dp[i][j]=1ll*dp[i-1][j]*(2*j-c0-j)%mod;
c0++;
}
else
{
for(int j=0;j<=n;j++)if(dp[i-1][j])
{
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
for(int k=j+1;k<=n;k++)
dp[i][k]=(dp[i][k]+1ll*dp[i-1][j]*(k-j+1)%mod*binom[c1-j][k-j-1]%mod*g[k-j-1]%mod)%mod;
}
c1++;
}
}
int ans=dp[m][n];
for(int i=1;i<=n;i++)ans=1ll*ans*inv2%mod;
cout<<ans;
return 0;
}