题目大意

有一个长度为 $N$ 的环形 01 串，每次变化规则为：

如果一个位置恰好有一个相邻位置为 1，则该位置下一轮变为 1

否则变为 0

给定初始状态和变化次数 $T$（$T$ 可达 $10^{15}$），求最终状态。

算法思路

核心思想

二进制倍增（矩阵快速幂思想），利用线性变换的性质。

关键观察

变化规则实际上是线性运算（在 $\mathbb{F}_2$ 上）：

设当前状态为向量 $v$

一次变化相当于 $v'[i] = v[i-1] \oplus v[i+1]$（下标模 $N$）

这可以表示为矩阵乘法：$v' = M \cdot v$

倍增优化

由于 $T$ 极大，直接模拟不可行。但线性变换具有结合律：

$T$ 次变化 = $M^T \cdot v$

将 $T$ 二进制分解：$M^T = M^{b_k} \cdot M^{b_{k-1}} \cdots M^{b_0}$

预处理 $M^{2^k}$，然后组合

实现技巧

在代码中：

las 和 cur 交替表示当前状态

按 $T$ 的二进制位从高到低处理

对于第 $i$ 位（对应 $2^i$ 次变换）：

状态更新：$v_{\text{new}}[j] = v_{\text{old}}[(j - 2^i) \bmod N] \oplus v_{\text{old}}[(j + 2^i) \bmod N]$

这相当于将旧状态旋转后异或

算法流程

读入 $N$, $T$ 和初始状态

从高位到低位遍历 $T$ 的二进制位：

如果该位为 1，则进行 $2^i$ 次变换的复合

通过旋转和异或实现线性变换

输出最终状态

复杂度分析

时间复杂度：$O(N \log T)$，每次变换 $O(N)$，共 $\log T$ 次

空间复杂度：$O(N)$，存储两个状态数组

总结

本题是线性递推 + 二进制倍增的经典应用：

问题转化：将细胞自动机规则转化为线性变换

倍增思想：利用二进制分解处理大指数

模运算优化：通过旋转操作避免矩阵乘法

位运算技巧：在 $\mathbb{F}_2$ 上用异或实现加法

这种"线性变换 + 快速幂"的方法适用于许多具有线性性质的递推问题，特别是当步数极大时的优化计算。