专栏文章

题解：P7213 [JOISC 2020] 最古の遺跡 3

居居然有个高手
P7213题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipxeo9k
此快照首次捕获于
2025/12/03 19:30
3 个月前
此快照最后确认于
2025/12/03 19:30
3 个月前
查看原文
观察原序列与最终保留序列的关系：首先原序列中 hi=nh_i = n 的两个位置中靠后的位置一定会保留下来。原因是它后面的位置再出现一个 nn。此刻靠前的位置变为 n−1n-1。
然后再加入原序列中 hi=n−1h_i = n-1 的两个位置，现在这三个位置中最靠后的也会被保留下来，原因相同。再往后加入 hi∈[1,n−2]h_i \in [1,n-2] 之后的结论是类似的。
这告诉我们，最终保留下来的序列可以由以下操作得到：按值域从大往小，每次填进新的两个位置后，选择最大的位置保留下来并删除。
下文中称出现在 aia_i 中的位置为应保留下来的位置，并记 pip_i 为 >ai>a_i 的不应保留下来的位置的个数，qiq_i 为 <ai<a_i 的不应保留下来的位置的个数（即 ai−ia_i -i）。
容易发现，若目前最小的未保留下的应保留下来的位置为 aia_i，那么我们就不能选取 >ai>a_i 的不应保留下来的位置，否则一定会错误保留一个位置。同时，<ai<a_i 的不应保留下来的位置可以任取，其不会影响后面的保留情况。
这启发我们记录状态 fi,j,k,0/1f_{i,j,k,0/1} 表示目前填入了 2i2i 个数，其中最小的未保留下来的应保留下来的位置为题面中的 aja_j，<aj<a_j 的不应保留下来的位置还有 kk 个未被填入，且 aja_j 的填入情况为 0/10/1 时的方案数。
那么，我们可以算出 ≥aj\ge a_j 且还未被填入的 axa_x 有 c=2(n−i)−pj−kc=2(n-i)-p_j-k 个。≥aj\ge a_j且已被填入且已被保留的 aya_y 有 o=i−j+1o=i-j+1 个。原因是 >aj>a_j 的不应保留的位置全部未被填入，且 <aj<a_j 的应保留位置已全部填入并保留。
考虑每次填入两个值，我们可以填入 ≥aj\ge a_j 的应保留值或 <aj<a_j 的不应保留值。容易发现，当 aja_j 未填入时，其变为被保留当且仅当填入 aja_j 与一个 <aj<a_j 的不应保留值；aja_j 已填入时，其变为被保留当且仅当填入两个 <aj<a_j 的不应保留值。
当最小的不应保留值变化时，我们还需要枚举其变化量 ll，此时应从拿出若干个上文提到的 aya_y 填在 [j+1,l][j+1,l]。但我们发现 aya_y 出现重复情况时其并非简单的 nn 选 mm 排列，但也无法暴力记录；不过 aya_y 最多只会出现两个重复值，因此我们视为填入的 hih_i 是 [1,2n][1,2n] 的排列，最后再将答案除以 2n2^n 可得到原答案。
现在可以开始转移了！对于 fi,j,k,0f_{i,j,k,0}，我们有以下转移：
fi,j,k,0→fi+1,j,k,0f_{i,j,k,0} \to f_{i+1,j,k,0}，即填入两个 >aj>a_j 的应保留值，要求 c≥3c\ge 3。
fi,j,k,0×2→fi+1,j,k,1f_{i,j,k,0} \times 2 \to f_{i+1,j,k,1}，即填入 aja_j 与一个 >aj>a_j 的应保留值。要求 c≥2c\ge 2。
fi,j,k,0×k×2→fi+1,j,k−1,0f_{i,j,k,0}\times k\times 2 \to f_{i+1,j,k-1,0}，即填入一个 >aj>a_j 的应保留值与一个 <aj<a_j 的不应保留值，要求 c≥2,k≥1c\ge 2,k\ge 1。
fi,j,k,0×k×2→fi+1,j,k−1,1f_{i,j,k,0}\times k\times 2\to f_{i+1,j,k-1,1}，即填入 aja_j 与一个 <aj<a_j 的不应保留值，要求 k≥1k\ge 1，并且还有一个 >aj>a_j 的已填入值还未被保留，即 n−j+1−c>on-j+1-c > o。
fi,j,k,0×k×(k−1)→fi+1,j,k−2,0f_{i,j,k,0}\times k\times(k-1)\to f_{i+1,j,k-2,0}，即填入两个 <aj<a_j 的不应保留值，要求 k≥2k\ge 2，同样要求 n−j+1−c>on-j+1-c > o。
fi,j,k,0×k×2×Al−j−1o→fi+1,l,p,0f_{i,j,k,0}\times k\times 2\times A_{l-j-1}^o \to f_{i+1,l,p,0}，其中 p=k−1+ql−qjp = k-1 + q_l - q_j，即填入 aja_j 与一个 <aj<a_j 的不应保留值，并且此时 aja_j 被保留。枚举下一个未被填入的值 ll，则带的权值为从 oo 中选 l−j−1l-j-1 个填给 [j+1,l−1][j+1,l-1]。要求 k≥1,n−j+1−c=ok\ge 1,n-j+1-c=o。
对于 fi,j,k,1f_{i,j,k,1}，有如下转移：
fi,j,k,1→fi+1,j,k,1f_{i,j,k,1}\to f_{i+1,j,k,1}，即填入两个 >aj>a_j 的应保留值，要求 c≥2c\ge 2。
fi,j,k,1×k×2→fi+1,j,k−1,1f_{i,j,k,1} \times k\times 2 \to f_{i+1,j,k-1,1}，即填入一个 >aj>a_j 的应保留值与一个 <aj<a_j 的不应保留值，要求 c≥1,k≥1c\ge 1,k\ge 1。
fi,j,k,1×k×(k−1)→fi+1,j,k−2,1f_{i,j,k,1}\times k\times (k-1)\to f_{i+1,j,k-2,1}，即填入两个 <aj<a_j 的不应保留值。要求 k≥2k\ge 2，且有一个 >aj>a_j 的应保留值已被填入且未被保留，即 n−j+1−c>o+1n-j+1-c>o+1。
fi,j,k,1×k×(k−1)×Al−j−1o→fi+1,l,p,0f_{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+ql−qjp=k-2+q_l-q_j，即填入两个 <aj<a_j 的不应保留值。且 aja_j 恰好在本回合被保留，同样枚举下一个未被填入的应保留值 ll，从 oo 中选 l−j−1l-j-1 个填给 [j+1,l−1][j+1,l-1]。要求 k≥2k\ge 2 且 n−j+1−c=o+1n-j+1-c=o+1。
容易发现两种需要枚举 ll 的转移要求会导致在 i,ji,j 固定时 kk 也固定，因此产生的转移量仅为 O(n3)O(n^3) 级别。
上述转移需要滚动数组进行空间复杂度的优化。本题得到解决。
时间复杂度：O(n3)O(n^3)，空间复杂度：O(n2)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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...