ABC 241E - Putting Candies（循环节：链+环）

https://zhuanlan.zhihu.com/p/473078132
这位大佬的E解释的非常清楚，强推

E - Putting Candies
https://atcoder.jp/contests/abc241/tasks/abc241_e

题目大意:
给定一个长度为n数组a: a[0] a[1] a[2] a[3]......a[n-1]。

初始有一个数 X=0，每次我们执行X+=a[X%n]，问在执行 K次操作后，X的值。

Sample Input 1  
5 3
2 1 6 3 1
Sample Output 1  
11

Sample Input 2  
10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202
Sample Output 2  
826617499998784056

模拟一下第一个图可知：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL N=200200,M=2002;
LL a[N],id[N],pre[N],n,k,st,ed;
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>k;
        for(LL i=0;i<n;i++)
            cin>>a[i];
        //初始化大家都是独立的个体
        for(LL i=0;i<N;i++)
            id[i]=-1;
        id[0]=0;//第一个位置上不论余什么都还是0
        //找循环节
        for(LL i=0;i<n;i++)
        {
            pre[i+1]=pre[i]+a[pre[i]%n];
            if(id[pre[i+1]%n]!=-1)
            {
                st=id[pre[i+1]%n];
                ed=i+1;
                break;
            }
            id[pre[i+1]%n]=i+1;
        }
        LL ans=0;
        if(k<=st) ans=pre[k];
        else
        {
            LL len=ed-st;
            LL X=pre[ed]-pre[st];
            LL A=(k-st-1)/len;
            LL B=(k-st-1)%len;
            ans=pre[st+B+1]+A*X;
        }
        cout<<ans<<endl;
    }
    return 0;
}