E - Putting Candies（思维，周期性）

题目链接：E - Putting Candies (atcoder.jp)

题目大意

给定一个长度为 N 的序列，X 从 0 开始，sum 一开始是0，进行 K 次操作，每次将 A[X] 加到 sum 中，并更新 X = sum % N。求最后的 sum。

数据范围详见原题。

思路

K的范围较大，但是N的范围较小，所以考虑从N入手。K远大于N，所以大概率会出现重复的X，而且重复出现的X的状态和之前的一样，所以会有周期性，可以找出周期T，然后利用T和K之间的关系倍增，再加上剩下的 m 次操作。

注意周期不一定从第一位开始，假设从第 P 位开始，到第P + T - 1位（共T个元素）是一个周期，从第P + T开始第二个周期，那么[1, P - 1]的元素就是“非周期内”元素，需要去除掉。

代码

/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long
//请使用%lld输出long long类型数据
using namespace std;
inline int re(){
	int s = 0,w = 1;char c = gc();
	while(c > '9' || c < '0'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
/*-------全局变量------*/
const int maxn = 2e5 + 10;
int N, K, A[maxn], last[maxn], sum[maxn];
/*-----自定义函数------*/

signed main()
{
	//freopen("in.txt","r",stdin);
	N = re(), K = re();	
	for(int i = 0;i < N; ++ i)A[i] = re();
	//input finished
	int X = 0, ans = 0, m = 0;
	for(int i = 0;i < K; ++ i)
	{
		if(last[X])//这个点已经走过了 
		{
			int T = i - last[X];
			ans += (ans - sum[last[X] - 1]) * ((K - last[X]) / T - 1);//减去非周期内的一部分和，得到的就是一个周期的和，乘以周期数 
			m = (K - last[X]) % T;
			X = ans % N;
			break;
		}
		last[X] = i;
		X = (sum[i] = (ans += A[X])) % N;
	}
	//进行剩下的 m 次操作 (m < N)
	while(m --)X = (ans += A[X]) % N;
	pr("%lld\n",ans);
	return 0;
}