专栏文章

题解：AT_abc384_d [ABC384D] Repeated Sequence

LLiuhy2996
AT_abc384_d题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miqrzhch
此快照首次捕获于
2025/12/04 09:46
3 个月前
此快照最后确认于
2025/12/04 09:46
3 个月前
查看原文

思路

先让 SS 模周期的和，然后在 A1A_1 到 A2NA_{2N} 中看有没有一段和为 SS。可以求个前缀和，然后枚举右端点，用 map 维护出现过的左端点，判断是否存在 sl=sr−Ss_l=s_r-S 即可。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+10;
int n,s,a[N];
map<int,bool>mp;
signed main(){
	cin>>n>>s;
	for(int i=1;i<=n;++i) cin>>a[i],a[i+n]=a[i];
	for(int i=1;i<=n*2;++i) a[i]+=a[i-1];
	s%=a[n];
	for(int i=0;i<=n*2;++i){
		mp[a[i]]=1;
		if(mp[a[i]-s]) cout<<"Yes",exit(0);
	}
	cout<<"No";
	return 0;
}

评论

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

正在加载评论...