题解：AT_abc384_d [ABC384D] Repeated Sequence

Liuhy2996 · 2024-12-15 09:45:26 · 题解

思路

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

代码

#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;
}