P9661 [ICPC 2021 Macao R] Sandpile on Clique 題解

DengDuck · 2026-05-12 08:12:35 · 题解

原創做法，非常優雅。

注意到每次操作對於所有數字只有 +1 和 -n+1 兩種情況，換而言之，在模 n 意義下所有數字 +1。

那麼，同樣的同餘等價類最終的值顯然是一樣的（如果不一樣說明有數字 x(x\geq n)，那就倒閉了），而且每個位置之間模意義下的差值肯定不變。

由此我們想到如果操作次數到 n 都找不到定局就說明沒有定局，原因顯然。

我們枚舉操作次數 i，用一些計數小技巧可以算出所有數字 +i 之後在模 n 意義下的和，我們判定這個和是否和原來的所有數字之和，再判定一下有沒有出現 n-1 即可。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e5+5;
int n;
LL A[N],B[N],S[N],Sum,K;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
        B[A[i]%n]++;
        K+=A[i]%n;
        Sum+=A[i];
    }
    for(int i=0;i<n;i++)S[i]=S[i-1]+B[i];
    for(int i=0;i<n;i++)
    {
        LL Sum2=K+1ll*i*n-(S[n-1]-S[n-1-i])*n;
        if(Sum2==Sum&&!B[n-1-i])
        {
            for(int j=1;j<=n;j++)cout<<(A[j]+i)%n<<' ';
            return 0;
        }
    }
    cout<<"Recurrent"<<endl;
}