题解：P7213 [JOISC 2020] 最古の遺跡 3
居然有个高手
·
·
题解
观察原序列与最终保留序列的关系：首先原序列中 h_i = n 的两个位置中靠后的位置一定会保留下来。原因是它后面的位置再出现一个 n。此刻靠前的位置变为 n-1。
然后再加入原序列中 h_i = n-1 的两个位置，现在这三个位置中最靠后的也会被保留下来，原因相同。再往后加入 h_i \in [1,n-2] 之后的结论是类似的。
这告诉我们，最终保留下来的序列可以由以下操作得到：按值域从大往小，每次填进新的两个位置后，选择最大的位置保留下来并删除。
下文中称出现在 a_i 中的位置为应保留下来的位置，并记 p_i 为 >a_i 的不应保留下来的位置的个数，q_i 为 <a_i 的不应保留下来的位置的个数（即 a_i -i）。
容易发现，若目前最小的未保留下的应保留下来的位置为 a_i，那么我们就不能选取 >a_i 的不应保留下来的位置，否则一定会错误保留一个位置。同时，<a_i 的不应保留下来的位置可以任取，其不会影响后面的保留情况。
这启发我们记录状态 f_{i,j,k,0/1} 表示目前填入了 2i 个数，其中最小的未保留下来的应保留下来的位置为题面中的 a_j，<a_j 的不应保留下来的位置还有 k 个未被填入，且 a_j 的填入情况为 0/1 时的方案数。
那么，我们可以算出 \ge a_j 且还未被填入的 a_x 有 c=2(n-i)-p_j-k 个。\ge a_j且已被填入且已被保留的 a_y 有 o=i-j+1 个。原因是 >a_j 的不应保留的位置全部未被填入，且 <a_j 的应保留位置已全部填入并保留。
考虑每次填入两个值，我们可以填入 \ge a_j 的应保留值或 <a_j 的不应保留值。容易发现，当 a_j 未填入时，其变为被保留当且仅当填入 a_j 与一个 <a_j 的不应保留值；a_j 已填入时，其变为被保留当且仅当填入两个 <a_j 的不应保留值。
当最小的不应保留值变化时，我们还需要枚举其变化量 l，此时应从拿出若干个上文提到的 a_y 填在 [j+1,l]。但我们发现 a_y 出现重复情况时其并非简单的 n 选 m 排列，但也无法暴力记录；不过 a_y 最多只会出现两个重复值，因此我们视为填入的 h_i 是 [1,2n] 的排列，最后再将答案除以 2^n 可得到原答案。
现在可以开始转移了！对于 f_{i,j,k,0}，我们有以下转移：
$f_{i,j,k,0} \times 2 \to f_{i+1,j,k,1}$，即填入 $a_j$ 与一个 $>a_j$ 的应保留值。要求 $c\ge 2$。
$f_{i,j,k,0}\times k\times 2 \to f_{i+1,j,k-1,0}$，即填入一个 $>a_j$ 的应保留值与一个 $<a_j$ 的不应保留值，要求 $c\ge 2,k\ge 1$。
$f_{i,j,k,0}\times k\times 2\to f_{i+1,j,k-1,1}$，即填入 $a_j$ 与一个 $<a_j$ 的不应保留值，要求 $k\ge 1$，并且还有一个 $>a_j$ 的已填入值还未被保留，即 $n-j+1-c > o$。
$f_{i,j,k,0}\times k\times(k-1)\to f_{i+1,j,k-2,0}$，即填入两个 $<a_j$ 的不应保留值，要求 $k\ge 2$，同样要求 $n-j+1-c > o$。
$f_{i,j,k,0}\times k\times 2\times A_{l-j-1}^o \to f_{i+1,l,p,0}$，其中 $p = k-1 + q_l - q_j$，即填入 $a_j$ 与一个 $<a_j$ 的不应保留值，并且此时 $a_j$ 被保留。枚举下一个未被填入的值 $l$，则带的权值为从 $o$ 中选 $l-j-1$ 个填给 $[j+1,l-1]$。要求 $k\ge 1,n-j+1-c=o$。
对于 $f_{i,j,k,1}$，有如下转移：
$f_{i,j,k,1}\to f_{i+1,j,k,1}$，即填入两个 $>a_j$ 的应保留值，要求 $c\ge 2$。
$f_{i,j,k,1} \times k\times 2 \to f_{i+1,j,k-1,1}$，即填入一个 $>a_j$ 的应保留值与一个 $<a_j$ 的不应保留值，要求 $c\ge 1,k\ge 1$。
$f_{i,j,k,1}\times k\times (k-1)\to f_{i+1,j,k-2,1}$，即填入两个 $<a_j$ 的不应保留值。要求 $k\ge 2$，且有一个 $>a_j$ 的应保留值已被填入且未被保留，即 $n-j+1-c>o+1$。
$f_{i,j,k,1}\times k\times (k-1)\times A_{l-j-1}^o\to f_{i+1,l,p,0}$，其中 $p=k-2+q_l-q_j$，即填入两个 $<a_j$ 的不应保留值。且 $a_j$ 恰好在本回合被保留，同样枚举下一个未被填入的应保留值 $l$，从 $o$ 中选 $l-j-1$ 个填给 $[j+1,l-1]$。要求 $k\ge 2$ 且 $n-j+1-c=o+1$。
容易发现两种需要枚举 $l$ 的转移要求会导致在 $i,j$ 固定时 $k$ 也固定，因此产生的转移量仅为 $O(n^3)$ 级别。
上述转移需要滚动数组进行空间复杂度的优化。本题得到解决。
时间复杂度：$O(n^3)$，空间复杂度：$O(n^2)$。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=605,mod=1e9+7,inv2=(mod+1)/2;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
int n,a[N],jie[N<<1],inv[N<<1],f[2][N][N][2],p[N];
inline int A(int n,int m){
return jie[n]*1ll*inv[n-m]%mod;
}
int main(){
n=read();
for(int i = 1;i<=n;i++)a[i]=read(),p[i]=(2*n-a[i])-(n-i);
jie[0]=jie[1]=inv[0]=inv[1]=1;
for(int i = 2;i<=n*2;i++)jie[i]=jie[i-1]*1ll*i%mod,inv[i]=inv[mod%i]*1ll*(mod-mod/i)%mod;
for(int i = 2;i<=n*2;i++)inv[i]=inv[i-1]*1ll*inv[i]%mod;
f[0][1][a[1]-1][0]=1;
a[n+1]=2*n+1;
for(int i = 0,now=0,nxt=1;i<n;i++,now^=1,nxt^=1){
memset(f[nxt],0,sizeof f[nxt]);
for(int j = 1;j<=n;++j){
for(int k = 0;k<=a[j]-j;k++){
int c = 2*n-2*i-p[j]-k,o = i - (j-1);
if(f[now][j][k][0]){
if(c>=3)f[nxt][j][k][0]=(f[nxt][j][k][0]+f[now][j][k][0])%mod;
if(c>=2){
f[nxt][j][k][1]=(f[nxt][j][k][1]+1ll*f[now][j][k][0]*2)%mod;
if(k)f[nxt][j][k-1][0]=(f[nxt][j][k-1][0]+1ll*f[now][j][k][0]*k*2)%mod;
}
if(n-j+1-c != o){
if(k)f[nxt][j][k-1][1]=(f[nxt][j][k-1][1] + 1ll*f[now][j][k][0]*k*2)%mod;
if(k>=2)f[nxt][j][k-2][0]=(f[nxt][j][k-2][0] + 1ll*f[now][j][k][0]*k*(k-1))%mod;
}
else if(k){
for(int l = j+1;l-j-1<=o;l++)f[nxt][l][k-1+(a[l]-l)-(a[j]-j)][0]=(f[nxt][l][k-1+(a[l]-l)-(a[j]-j)][0] + 1ll*f[now][j][k][0]*k*2%mod*A(o,l-j-1))%mod;
}
}
if(f[now][j][k][1]){
if(c>=2)f[nxt][j][k][1]=(f[nxt][j][k][1]+1ll*f[now][j][k][1])%mod;
if(c&&k)f[nxt][j][k-1][1]=(f[nxt][j][k-1][1]+1ll*f[now][j][k][1]*k*2)%mod;
if(k>=2){
if(n-j+1-c!=o+1)f[nxt][j][k-2][1]=(f[nxt][j][k-2][1]+1ll*f[now][j][k][1]*k*(k-1))%mod;
else{
for(int l = j+1;l-j-1<=o;l++)f[nxt][l][k-2+(a[l]-l)-(a[j]-j)][0]=(f[nxt][l][k-2+(a[l]-l)-(a[j]-j)][0] + 1ll*f[now][j][k][1]*k*(k-1)%mod*A(o,l-j-1))%mod;
}
}
}
}
}
}
for(int i = 1;i<=n;i++)f[n&1][n+1][0][0]=1ll*f[n&1][n+1][0][0]*inv2%mod;
cout<<(f[n&1][n+1][0][0]+mod)%mod;
return 0;
}
```