← 返回题目列表

Codeforces · 1344/A

A. 希尔伯特酒店

中文机器翻译题面 查看原题

希尔伯特酒店是一家非常不寻常的酒店,因为房间数量是无限的!事实上,每个整数都有一个空间,包括零和负整数。更奇怪的是,酒店目前已满员,这意味着每个房间里只有一名客人。酒店经理大卫希尔伯特本人决定对客人进行洗牌,因为他认为这会产生空位(没有客人的房间)。

对于任何整数 $$$k$$$ 和正整数 $$$n$$$,设 $$$k\bmod n$$$ 表示 $$$k$$$ 除以 $$$n$$$ 所得的余数。更正式地说, $$$r=k\bmod n$$$ 是最小的非负整数,使得 $$$k-r$$$ 可以被 $$$n$$$ 整除。它总是成立 $$$0\le k\bmod n\le n-1$$$。例如,$$$100\bmod 12=4$$$ 和 $$$(-1337)\bmod 3=1$$$。

然后洗牌工作如下。有一个 $$$n$$$ 整数 $$$a_0,a_1,\ldots,a_{n-1}$$$ 数组。然后,对于每个整数$$$k$$$,房间$$$k$$$中的客人被移动到房间号$$$k+a_{k\bmod n}$$$。

在此洗牌过程之后,确定是否仍然恰好有一名客人分配到每个房间。也就是说,没有空房或有多名客人入住的房间。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。接下来的 $$$2t$$$ 行包含测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_0,a_1,\ldots,a_{n-1}$$$ ($$$-10^9\le a_i\le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果在洗牌过程后只有一名客人分配给每个房间,则输出包含“YES”的单行,否则输出“NO”。您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

6
1
14
2
1 -1
4
5 5 5 1
3
3 2 1
2
0 1
5
-239 -2 -100 -3 -11

输出 #1

YES
YES
YES
NO
NO
YES

注意

在第一个测试用例中,每位客人都被转移 $$$14$$$ 个房间,因此分配仍然是唯一的。

在第二个测试用例中,偶数客人向右移动 $$$1$$$ 房间,奇数客人向左移动 $$$1$$$ 房间。我们可以证明该作业仍然是唯一的。

在第三个测试用例中,每四位客人向右移动 $$$1$$$ 个房间,其他客人向右移动 $$$5$$$ 个房间。我们可以证明该作业仍然是唯一的。

在第四个测试用例中,客人 $$$0$$$ 和 $$$1$$$ 都被分配到房间 $$$3$$$。

在第五个测试用例中,客人 $$$1$$$ 和 $$$2$$$ 都被分配到房间 $$$2$$$。