题面

挂个 pdf
题面下载

算法

分析题目发现, 一次进化等效于:
在 \(a\) 两端加 \(0\)
对于 \(i \in [1, n], a_i \leftarrow a_{i - 1} \oplus a_{i + 1}\)

于是猜测在 \(k\) 次操作之后
有 \(a_i \leftarrow a_{i + k} \oplus a_{i - k}\)
代入计算后发现这个式子显然错误, 原因是当 \(k\) 足够大时, \(a\) 显然会变成全 \(0\), 但这不符合题意
考虑构造一个环, 这样在进化时就不会超出范围

对于\(i = 0\), 其左侧需要一个 \(a_{i + 1}\), 对于其左侧, 需要一个 \(a_{i + 2}\), 最后会变成一个环 \(c\)

以下 \(l_i\) 表示向左移动 \(i\), \(r_i\) 表示向右移动 \(i\)
观察 \(T = 1\)
此时答案为 \(l_1 \oplus r_1\)
观察 \(T = 2\)
此时答案为 \((l_2 \oplus c) \oplus (c \oplus r_2) = l_2 \oplus r_2\)
观察 \(T = 3\)
发现消不掉
观察 \(T = 4\)
发现为 \(l_4 \oplus r_4\)

所以对于 \(T = 2^d\), 答案为 \(l_{2^d} \oplus r_{2^d}\)
对于其他 \(T\), 二进制拆分之后将答案异或即可, 时间复杂度 \(O(n \log T)\)

代码

总结

变换类题目, 一般要构造循环节 / 环状结构
对于一些式子, 若没有较好的通项公式, 考虑枚举之后找规律