Codeforces Round 639 Div.2

这场div本来应该在5月3日举办，结果因为数据库问题被挪到了5月6日。没想到当天，CF又挂了！！！漫长的队列导致一次提交可能要在半个小时甚至多个小时之后才能看到结果，于是这场比赛变成了unrated。不过这对我来说是个好事（明明是必须这样好吗），因为我的B题在提交后半个小时才返回WA结果，然后我检查代码发现打表打小了……于是又补交了一发，直到比赛结束的时候我都没有看见评测结果，第二天醒来才看见AC……总之这是一次体验糟糕的比赛。

另B被人用暴力水过了……

C - Hilbert’s Hotel

这题其实非常简单，比赛的时候想到了正解，不过不知道怎么验证。第二天YGL告诉我这样写就OK，我就认真想了下，好像确实是这么一回事。

虽然考虑的整数是无穷的，但是我们可以人为的把它划分成长度为$n$的周期，题目其实就是对一个周期中的数按照$a[]$的值进行偏移。那么什么时候会空出房间呢？显然是两个不同不同的数在偏移过后得到了相同的结果呗。用数学的方式来表示，那就是

$$ i+nk_i+a_i=j+nk_j+a_j $$

其中$i,j\in[0,n-1]$，$k$则是它们各自所在的周期位置，那么$i+nk_i$就是其对应的初始数字，然后我们再加上它的偏移量$a_i$，得到的就是偏移后的心的位置，对于$j$也是如此。

那么很显然，上述式子仍然具有周期性，我们可以对等式两边取模

$i+nk_i+a_i=j+nk_j+a_j$

$(i+nk_i+a_i)\% n=(j+nk_j+a_j)\% n$

$(i+a_i)\% n=(j+a_j)\% n$

也就是说我们只需要判断一个周期$[0,n-1]$的重叠情况就可以了。

当然这里存在一点细节，由于C/Java使用的是$Truncate$除法，所以如果负数对正数取模时，得到的结果可能是负数，实际编写时，为了防止下标越界，我们应该进一步处理

$(i+a_i)\% n=(j+a_j)\% n$

$((i+a_i)\% n+n)\% n=((j+a_j)\% n+n)\% n$

取模在不同语言下得到的结果可能不同，这取决于语言遵循的取整方式，详细内容可以参考《负数取模怎么算》

/**
  * @Project Codeforces_Round__639__Div__2_
  * @Filename Hilberts_Hotel
  * @Author Visors
  * @Date 2020/5/8 11:26
  * @Version 1.0
  * @Description TODO
  **/

#include <iostream>
#include <vector>

using namespace std;
int T, n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        vector<int> v(n);
        vector<bool> book(n, false);
        for (auto &it:v) cin >> it;
        for (int i = 0, tmp; i < n; i++) {
            tmp = (((v[i] + i) % n) + n) % n; //避免%出负数
            if (!book[tmp]) book[tmp] = true;
            else {
                cout << "NO" << endl;
                goto over;
            }
        }
        cout << "YES" << endl;
        over:;
    }
    return 0;
}