专栏文章

题解：P12538 [XJTUPC 2025] 泰拉构史

EELECTRODE_kaf
P12538题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip3tpds
此快照首次捕获于
2025/12/03 05:42
3 个月前
此快照最后确认于
2025/12/03 05:42
3 个月前
查看原文
设 dpi,x,ydp_{i,x,y} 表示考虑 a1a_1 到 aia_i，序列最后两位分别为 xx 和 yy 的方案数。
考虑 dpi−1,x,ydp_{i-1,x,y} 对于 dpidp_i 的贡献。序列中的每一位都不同，所以一个 aa 只能和 a+1a+1 和 a−1a-1 换位，所以序列最后三项只有一下情况：
CPP
x    y    a[i]（1）
x    a[i] y   （2）
y    x    a[i] (*)
y    a[i] x    (*)
a[i] x    y   （3）
a[i] y    x    (*)
为了避免重复计算，打（*）的情况无需考虑。
情况（1）没有限制条件，累加 dpi−1,x,ydp_{i-1,x,y} 对 dpi,y,aidp_{i,y,a_i} 的贡献。
因为换位只能换相邻位置上的数，所以情况（1）首先要变为情况（2），然后变为情况（3）。
情况（1）变为情况（2）的条件是 ∣ai−y∣=1|a_i-y|=1，若符合则累加 dpi−1,x,ydp_{i-1,x,y} 对 dpi,ai,ydp_{i,a_i,y} 的贡献。
情况（2）变为情况（3）的条件是 ∣ai−x∣=1|a_i-x|=1，若同时符合两次转化的条件则累加 dpi−1,x,ydp_{i-1,x,y} 对 dpi,x,ydp_{i,x,y} 的贡献。
最终答案即为 ∑dpn\sum dp_n。
CPP
const ll N=1e6+10,mod=998244353;
ll n,a[N];
map<pll,ll> dp[N];

bool check(ll x,ll y) {
	return abs(x-y)==1;
}

int main() {
	cin>>n;

	rep(i,1,n) cin>>a[i];

	dp[0][ {-1,-1}]=1;

	rep(i,1,n) {
		for(auto [num,sum]:dp[i-1]) {
			ll x=num.fi,y=num.se;
			(dp[i][ {y,a[i]}]+=sum)%=mod;

			if(check(y,a[i])) {
				(dp[i][ {a[i],y}]+=sum)%=mod;

				if(check(x,a[i])) (dp[i][num]+=sum)%=mod;
			}
		}
	}

	ll ans=0;

	for(auto [num,sum]:dp[n]) (ans+=sum)%=mod;

	cout<<ans;
}

评论

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

正在加载评论...