自动搬运

查看原文

来自洛谷，原作者为

	Shunpower 我笨笨的，菜菜的，累累的 >_< | 在役

搬运于2025-08-24 23:16:27，当前版本为作者最后更新于2025-06-16 11:39:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单题。

考虑把下标转移到 $0\sim n-1$，那么每次传球实际上是先让 $x\gets 1$，之后循环进行 $x\gets (x+a_i)\bmod n$。我们就是要找这个过程中所有 $x$ 中 $c_x$ 最小的。

容易想到把整段整段的 $a_i$ 全部取下来，换句话说，我们对 $a$ 垒前缀和记作 $s$，那么最终到达的位置实际上可以表示成 $(1+ks_m+s_i)\bmod n$。

记最终到达的位置是 $p$，展开式子有 $k_1n+p=k_2s_m+s_i$，移项得到二元一次不定方程形式：

因为 $p$ 在 $\bmod n$ 剩余系意义下，所以符号不重要。合法的 $p$ 只需使得方程有解即可。由裴蜀定理取 $g=\gcd(n,s_m)$，可知 $g|p-s_i$。

容易发现如果我们已知 $g$，那么可以轻易做到在线加入 $s_i$：记忆化地往两边 $\pm g$ 跳跃，做贡献标记即可，总时间复杂度 $\mathcal O(n+q)$。于是按照 $g$ 离线即可 $\mathcal O((n+q)d(n))$。

int n,q;
int p[N];
int a[N];
bool vis[N];
bool keyn[N];
int res[N];
int ans;
int g;
vector <int> ofl[N];
void gocheck(int x){
	// cout<<"!"<<x<<endl;
	if(vis[x]) return;
	vis[x]=1;
	ans=min(ans,p[x]);
	gocheck((x+g)%n);
	gocheck((x+n-g)%n);
}
int main(){
#ifdef Shun
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	ios::sync_with_stdio(false);
	cin>>n>>q;
	fr1(i,0,n-1) cin>>p[i];
	fr1(i,1,q) cin>>a[i],(a[i]+=a[i-1])%=n;
	fr1(i,1,q) ofl[__gcd(n,a[i])].pb(i);
	fr1(i,1,n){
		if(ofl[i].empty()) continue;
		fr1(j,0,n-1) vis[j]=0;
		fr1(j,1,q) keyn[j]=0;
		for(auto j:ofl[i]) keyn[j]=1;
		g=i;
		ans=1e9;
		fr1(j,1,q){
			gocheck(a[j]);
			if(keyn[j]){
				res[j]=ans;
			}
		}
	}
	fr1(i,1,q) cout<<res[i]<<' ';
	ET;
}
//ALL FOR Zhang Junhao.