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 步的“累计跳跃长度”:

S_k = b_0 + b_1 + \cdots + b_{k-1} \quad (\text{取模 } n)

- 如果对某个 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 的值:

S_n = 2 \cdot c_2 + 3 \cdot c_3 \\ = 2 \cdot c_2 + 3 \cdot (n - c_2) \\ = 3n - c_2 \\ \implies S_n \mod n \equiv -c_2 \mod 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 = 2p + 3q = 3k - p.

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 步时回到起点,形成小圈:

n \mod  3 = r

c_2 \mod 6 = m

结果

0

0 或 1

No

1

4 或 5

No

2

2 或 3

No

其他组合

其他值

Yes

为什么只看 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))

这就是我