J. message
问题描述
有 n 个孩子围成一圈玩传话游戏。孩子们从 0 到 n-1 编号，每个孩子都面向圆心。
每个孩子都拿着一张卡片。第 i 个孩子的卡片上有一个数字 a_i，其中a_i \in \{2, 3\}。
如果第 i 个孩子收到消息，他们会把消息传给编号为(i + a_i) \mod n的孩子。
老师想通知其中一个孩子，使得最终每个孩子都能收到消息。你的任务是帮助老师重新排列孩子们的位置，并选择一个孩子首先接收消息。判断是否可能通过这种方式确保所有孩子都能收到消息。
输入
- 第一行包含一个正整数 T 1 \leq T \leq 10⁵)，表示测试用例的数量。
- 对于每个测试用例：
- 第一行包含一个正整数 n 1 ≤ n ≤ 10⁵)，表示孩子的数量。
- 下一行包含 n 个正整数 aᵢ，每个数是 2 或 3，表示每个孩子卡片上的数字。
- 保证所有测试用例的 n 的总和 Σ n) 不超过10⁶。
输出
对于每个测试用例，输出一行包含 "Yes" 或 "No"，表示是否可能通过重新排列孩子的位置，并在告知其中一个孩子消息后，让每个孩子都收到消息。
示例
标准输入
3
3
2 3 2
4
2 2 2 2
6
3 2 3 2 3 3标准输出
Yes
No
Yes注意
对于第一个测试用例，不需要重新排列；只需选择将消息告诉第一个孩子（编号为
0的孩子）即可实现目标。对于第二个测试用例，可以证明目标无法实现。
对于第三个测试用例，通过将序列重新排列为
3 3 3 2 2 3并将消息告诉编号为1的孩子，可以实现目标。
题解
我们先把老师允许的“重新排列孩子”＋“选一个孩子先接收消息”这一操作，等价地看成：
- 在环上按顺序放置一个长度为 n 的序列 b_0, b_1, \ldots, b_{n-1} ，其中每个 b_i \in \{2, 3\} ，且两者的个数必须和给定的相同（共 c_2 个“2”、c_3 = n - c_2 个“3”）。
- 起点固定为下标 0 ，从 0 出发，若当前在位置 j ，就跳到 (j + b_j) \mod n 。
要让“每个孩子都能收到消息”，当且仅当这条跳转路径恰好是一条 长度恰好为 n 的单圈，也就是：
1. 不早于第 n 步回到起点（否则会先形成一个长度 < n 的小圈，剩下的孩子永远收不到）；
2. 第 n 步一定要回到起点（否则跑满 n 步都没回到起点，也不会覆盖所有节点）。
记前 k 步的“累计跳跃长度”：
- 如果对某个 1 \leq k < n ，恰有 S_k \equiv 0 \pmod{n} ，那么前 k 步就回到起点，形成小循环 → 失败。
- 如果累计到第 n 步的和 S_n \equiv 0 \pmod{n} ，则第 n 步才能回到起点，满足“恰好 n 步回到起点”的必要条件；但还要同时保证所有 1 \leq k < n 时 S_k \leq 0。
下面我们来看 S_n 的值：
由于 0 \leq c_2 < n ，所以只有当 c_2 = 0 （即所有卡片都是 3）时，才会 S_n \equiv 0 。
若 c_2 = 0 ，则每一步都是跳 3 格，等价于映射 i \to i + 3 \pmod{n} ，这会把环分成 g = \gcd(n, 3) 个小圈，显然不能覆盖全体。
接下来，我们要排除那种“某个 k < n 使 S_k \equiv 0 ”的情况。记在前 k 步中用了 p 个“2”（和 q = k - p 个“3”），则
要 S_k \equiv 0 \iff 3k - p \equiv 0 \pmod{n} \iff p \equiv 3k \pmod{n} 。
因为 1 \leq k \leq n-1 且 0 \leq p \leq k ，我们可以对 k 和 p 在有限范围内暴力枚举，或者更巧妙地直接对
- n \mod 3 （记作 r \in \{0, 1, 2\} ）
- c_2 \mod 6 （记作 m \in \{0, 1, 2, 3, 4, 5\} ）
有限范围枚举：
import itertools
ns = 15
for n in range(1,ns + 1):
cnt2s = set()
for cnt2 in range(n+1):
for positions in itertools.combinations(range(n), cnt2):
vis = set()
sequence = [3] * n
for idx in positions:
sequence[idx] = 2
p = 0
last = 0
while True:
last = len(vis)
p = (p+sequence[p]) % n
vis.add(p)
if last == len(vis):
break
vis.add(0)
if len(vis) == n:
cnt2s.add(cnt2)
print(f"{n}: {cnt2s}")
'''
n: {2的数量}
1: {0, 1}
2: {0, 1}
3: {2, 3}
4: {0, 1, 2, 3}
5: {0, 1, 4, 5}
6: {2, 3, 4, 5}
7: {0, 1, 2, 3, 6, 7}
8: {0, 1, 4, 5, 6, 7}
9: {2, 3, 4, 5, 8, 9}
10: {0, 1, 2, 3, 6, 7, 8, 9}
11: {0, 1, 4, 5, 6, 7, 10, 11}
12: {2, 3, 4, 5, 8, 9, 10, 11}
13: {0, 1, 2, 3, 6, 7, 8, 9, 12, 13}
14: {0, 1, 4, 5, 6, 7, 10, 11, 12, 13}
15: {2, 3, 4, 5, 8, 9, 10, 11, 14, 15}
每三组为一循环来看，就会发现每次循环后都会增加两项，前面保持不变
'''进行组合分析，发现 恰有下面 6 种(r, m) 会导致存在某个k<n 满足 3k - p \equiv 0 ，无论你怎么排列都逃不过在 k 步时回到起点，形成小圈：
为什么只看 c_2 \mod 6 ？因为在检测 S_k \equiv 0 时，p（前 k 步中用到的“2”的个数）与 k 共同决定 3k - p ；而 k 最多到 n-1 ， p \leq k \leq n-1 ，所以只和 c_2 的模 6 情况有关（具体枚举可知每 6 周期重复）。
为什么只看 n \mod 3 ？ 因为 3k - p \equiv 0 要求 3k \equiv p \pmod{n} ，而 3 与 n 是否能“裹回”到小圈，关键取决于 n 对 3 的余数情况。
最后，具体做法就是：
1. 读入 n 和序列，计算 c_2“2 的个数”。
2. 令 r = n \mod 3 ，m = c_2 \mod 6。
3. 如果 (r = 0 \text{ 且 } m \in \{0, 1\}) \text{ 或 } (r = 1 \text{ 且 } m \in \{4, 5\}) \text{ 或 } (r = 2 \text{ 且 } m \in \{2, 3\})，输出 “No”，否则输出 “Yes”。
整个算法对每个测试只需要 O(n) 统计一次，\sum n \leq 10^6，完全够用。
代码
import sys
input = sys.stdin.readline
T = int(input())
out = []
for _ in range(T):
n = int(input())
a = list(map(int, input().split()))
c2 = a.count(2)
r = n % 3
m = c2 % 6
if (r == 0 and m in (0,1)) or \
(r == 1 and m in (4,5)) or \
(r == 2 and m in (2,3)):
out.append("No")
else:
out.append("Yes")
print("\n".join(out))
