题解：P12557 [UOI 2024] Football

· · 题解

简单题。

考虑把下标转移到 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-s_i=-k_1n+k_2s

因为 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.