A. Hilbert’s Hotel(数学)

传送门

\(看了一下网上都没什么题解，自己写一篇吧,对你有帮助的话留个言吧~\)

\(\color{Orange}{----------------------分割------------------------}\)

\(\color{Green}{一、分析问题}\)

\(对于给定的n和数组a,其实是有循环存在的\)

\(比如[0,n)模n后余数必定是[0,n)\)

\([n,2n)模n后余数必定是[0,n)\)

\(现在我们的目的是判断是否所有数都是互不相等的。\)

\(\color{Orange}{二、举例子发现规律}\)

\(拿这组样例来说\)

\(4\)
\(5\ 5\ 5\ 1\)

\(按照我们上面的循环节，把操作后得到的数写出来\)

\([0,3]:5\ 6\ 7\ 4\)
\([4,7]:9\ 10\ 11\ 8\)
\(.............\)

\(可以发现,[4,7]就是由[0,3]都加n得来的，这很容易理解\)

\(那么我们可以把所有循环节看成由[0,3]加上nk得来的\)

\(所以现在的问题是已知集合={5+nk,6+nk,7+nk,4+nk},求是否有相同的数字\)

\(因为要互不相同,所以5、6、7、4模n后应该互不相等\)

\(\color{Red}{为什么?因为如果模n后相等，就一定存在某个k使得x_1=x_2+kn}\)

\(\color{Purple}{三、算法实现}\)

\(问题到这里应该就很简单了\)

\(先处理出[0,n)操作后得到的数字(也就是先处理一个循环节)\)

\(然后对处理后的每个数对n求余，如果余数互不相等说明不存在重复的数字\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
int n,t;
int a[maxn],b[maxn];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<n;i++)
            b[i]=i+a[i%n];//处理第一个循环节 
        for(int i=0;i<n;i++) b[i]=(b[i]%n+n)%n;//对n取余 
        sort(b,b+n);//排序后,如果余数互不相等,必定是0,1,2...n-1 
        int flag=1;
        for(int i=0;i<n;i++)
        if(b[i]!=i) flag=0;
        if(flag)    cout<<"YES";
        else    cout<<"NO";
        cout<<endl;
    }
}