题目链接: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; }
Comments NOTHING