P4804 题解 最后更新于 2025-05-02 00:00:45

## 题意 给定一个长度为 $n$ 的环，每个位置有一个数字 `0` 或 `1` 。每一轮变换中，环上每个数会变成上一轮中左右两边数字的异或值。求经过 $T$ 轮变换后环的状态。 $n\le 10^5,\ T\le 10^{15}$ ## 思路 有一个显然的结论：经过 $2^m$ 次变换后，每个位置上的值会变成变换前它的左边第 $2^m$ 个和右边第 $2^m$ 个数的异或值。 证明： 2 轮后：$a_i=(a_{i-2}\oplus a_{i})\oplus(a_{i}\oplus a_{i+2})=a_{i-2}\oplus a_{i+2}$ 4 轮后：$a_i=(a_{i-4}\oplus a_{i-2})\oplus(a_{i-2}\oplus a_{i})\oplus(a_{i}\oplus a_{i+2})\oplus(a_{i+2}\oplus a_{i+4})=a_{i-4}\oplus a_{i+4}$ ...... 然后对 $T$ 二进制拆分就做完了。时间复杂度 $O(n\log T)$ 。