专栏文章

题解：AT_s8pc_4_e Enormous Atcoder Railroad

MMeta_Morph
AT_s8pc_4_e题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio13nuj
此快照首次捕获于
2025/12/02 11:38
3 个月前
此快照最后确认于
2025/12/02 11:38
3 个月前
查看原文

AT_s8pc_4_e Enormous Atcoder Railroad 题解

博客园链接：AT_s8pc_4_e Enormous Atcoder Railroad 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

DP。

分析

fi,j,kf_{i,j,k} 表示长度为 ii 的区间，左边到原点距离为 jj，右边到原点距离为 kk 时方案数为多少。发现只需要求满足 j=k∨j+1=kj=k\lor j+1=k 的状态即可，那么有如下转移：
fi,j,j=∑len=12(X−j)fi−len,j,j+1+[i≤2(X−j)+1]fi,j,j+1=∑len=12(X−j)fi−len,j+1,j+1+[i≤2(X−j)]f_{i,j,j} = \sum_{len=1}^{2(X-j)} f_{i-len,j,j+1} + [i\le 2(X-j)+1] \\ f_{i,j,j+1} = \sum_{len=1}^{2(X-j)} f_{i-len,j+1,j+1} + [i\le 2(X-j)] \\
我们简化一下状态，设 fi,j,0/1′=fi,j,j/j+1f'_{i,j,0/1} = f_{i,j,j/j+1}，转移变为下式：
fi,j,0′=∑len=12(X−j)fi−len,j,1′+[i≤2(X−j)+1]fi,j,1′=∑len=12(X−j)fi−len,j+1,0′+[i≤2(X−j)]f'_{i,j,0} = \sum_{len=1}^{2(X-j)} f'_{i-len,j,1} + [i\le 2(X-j)+1] \\ f'_{i,j,1} = \sum_{len=1}^{2(X-j)} f'_{i-len,j+1,0} + [i\le 2(X-j)] \\
前缀和优化即可 O(Xmax⁡ΔS)O(X\max{\Delta S}) 解决。最后统计答案为：
∏i=0m−2fsi+1−si,i,1′\prod_{i=0}^{m-2} f'_{s_{i+1}-s_{i},i,1}

优化

发现空间太大，时间常数也太大，考虑把后两维 j,0/1j,0/1 一起滚动数组压掉，空间剩下 O(n)O(n)，时间常数极小。

代码

CPP
constexpr int N(1e4+10),M(2.5e3+10);

int n,m,X,ans,lim;
int a[M],f[N];

signed main() {
	/*DE("Input");*/
	I(n,m,X);
	if(m-1>X)return puts("0"),0;
	FOR(i,0,m-1)I(a[i]);
	FOR(i,0,m-2)tomax(lim,a[i+1]-a[i]);
	/*DE("DP");*/
	ans=1;
	DOR(j,X,0) {
		if(j<X) {
			DOR(i,lim,1) {
				f[i]=add(f[i-1],i<=2*(X-j));
				if(2*(X-j)<i)toadd(f[i],Mod-f[i-2*(X-j)-1]);
			}
			if(j<=m-2)tomul(ans,f[a[j+1]-a[j]]);
			FOR(i,1,lim)toadd(f[i],f[i-1]);
		}
		if(j>0) {
			DOR(i,lim,1) {
				f[i]=add(f[i-1],i<=2*(X-j)+1);
				if(2*(X-j)<i)toadd(f[i],Mod-f[i-2*(X-j)-1]);
			}
			FOR(i,1,lim)toadd(f[i],f[i-1]);
		}
	}
	/*DE("Output");*/
	O(ans,'\n');
	return 0;
}

评论

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

正在加载评论...