交发题解调了好久

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls u<<1
#define rs u<<1|1
#define lowbit(x) x&-x
const int N=2e5+10;
int n,k;
int a[N];
int vis[N];
int id[N];
int cnt[N];
int ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int x=0;
	int i=0;
	while(!vis[x%n]&&i<k){
		i++;
		vis[x%n]=1;
		id[x%n]=i;//当前的编号
		x+=a[x%n];//当前的
		cnt[i]=x;
	}
	if(i==k){
		cout<<x;
		return 0;
	}
	int r=i;
	int l=id[x%n];//循环l-1
	int need=k-i;//剩的次数
	int res=x-cnt[l-1];//一个循环贡献当前位置没有加
	int len=r-l+1;//循环长度
	ans+=x;//前面的
	ans+=(need/len)*res;//剩余能被整除的
	ans+=cnt[(need%len)+id[x%n]-1]-cnt[id[x%n]-1];//(need%len)接下来还要操作的次数,id[x%n]上一次的位置
	cout<<ans;
	return 0;
}
/*
思路一定会进入n的循环
*/

显而易见，我们甚至不能 $k(1 \leq k \leq 10^{12})$ 次模拟一遍。

不过很容易发现，在 $mod$ $n$ 这个操作下，最多 $n$ 次就一定会走入循环，后面就不需要模拟了。

具体怎么实现不就很简单了么。（代码能力不够就先放放，去刷几道模拟题。）

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T = 1;
const int N = 2e5 + 10;
int n, k;
int arr[N];
int tot;//x
int val[N];
bool vis[N];
map<int, int> mp;

void Solve() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int idx = 0, cnt = 0;

	while (!vis[idx] && cnt < k) {
		tot += arr[idx];
		vis[idx] = true;
		val[++cnt] = tot;
		mp[idx] = cnt;

		idx = tot % n;
	}

	if (cnt == k) {
		cout << tot;
		return;
	}

	int lef = k - cnt;//剩下多少次
	int loop = tot - val[mp[idx] - 1];//一个循环的贡献
	int tim = cnt - mp[idx] + 1;//一个循环需要多少次
	cout << tot + (lef / tim) * loop + (val[(lef % tim) + mp[idx] - 1] - val[mp[idx] - 1]);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	while (T--) {
		Solve();
	}
	return 0;
}