ABC 258 E Packing Potatoes

我的思路：

先像 ABC 167 D 一样把原问题转化为图上找环的问题。

将 $x\bmod \sum w_i$，将数组复制两遍，在数组上进行倍增。因为 $x< \sum w_i$，所以复制两遍原数组就应该够用了。每次位置如果 $\ge n$ 就模 $n$。

WA 了，求助大佬。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,q,x,w[N],sum=0,f[N<<1][22];
int st[N],top=0,hav[N],bef,tim;
inline void getcir(int pre)//找循环 
{
	if(hav[pre])//如果找到循环 
	{
		bef=hav[pre]-1;//最后一个非环上的点 
		tim=top-hav[pre]+1;//循环的周期 
		return;
	}
	++top;hav[pre]=top;
	int pos=pre,res=x;
	for(int i=20;i>=0;--i)
		if(f[pos][i]&&f[pos][i]<res)
			res-=f[pos][i],pos+=(1<<i);//倍增 
	++pos;st[top]=pos-pre;pos%=n;//st数组记录的是框内土豆个数 
	getcir(pos);
}
signed main()
{
	cin>>n>>q>>x;
	for(int i=0;i<n;++i)
	{
		cin>>w[i];sum+=w[i];
		f[i][0]=f[n+i][0]=w[i];
	}
	x%=sum;
	for(int i=1;i<=20;++i)//倍增预处理 
	{
		for(int j=0;j+(1<<i)-1<n+n;++j)
		{
			f[j][i]=f[j][i-1]+f[j+(1<<(i-1))][i-1];
		}
	}
    getcir(0);
	while(q--)
	{
		int u;cin>>u;
		if(u<=bef)cout<<st[u]<<endl;
		else cout<<st[bef+((u-bef)%tim?(u-bef)%tim:tim)]<<endl;
	}
	return 0;
}