题解：Bosco 与粒子

思路

先用 KMP 求每个振荡串的最短循环节。去掉重复周期后，粒子位置复原等价于全部振荡器 状态复原。

只保留某个振荡器时，从标准初态出发直到再次回到该状态，记向下、向上命中次数为 $(a_i',b_i')$。若全局周期中该振荡器被放大 $k_i$ 倍，则命中数为 $(k_i a_i',k_i b_i')$。相邻区间的往返次数相等，于是问题化为一条整除与比例链。

做法

子任务 1：完整状态模拟

记录粒子位置、方向和每个振荡器的字符指针，逐秒模拟直到回到初态。最短周期串的 状态空间很小，可直接完成。

子任务 2：逐质数稠密扫描

对每个质数 $p$，记边界次数的 $p$ 进指数为 $e_j$。通过第 $i$ 个振荡器要求

$$e_{i-1}\ge v_p(a_i'),\qquad e_i=e_{i-1}-v_p(a_i')+v_p(b_i').$$

从左到右扫描，若当前指数不足就整体抬高初始指数，得到最小可行 $e_0$。受限规模可枚举 所有质数并扫描所有振荡器。

满分算法：稀疏质因子事件

只在 $a_i'$ 或 $b_i'$ 含某质因子时建立事件。每个整数的不同质因子很少，因此事件总数 为线性对数级。对每个出现过的质数仅扫描其事件，即可得到初始边界次数 $T_0$ 的最小 质因数分解。

随后利用

$$T_i=T_{i-1}\cdot b_i'/a_i'$$

在模意义下递推所有边界次数。若首个 $b_i'=0$ 出现在下标 $i$，粒子不会越过该振荡器， 只需处理它之前的链。最终周期为

$$2\sum_{j=0}^{L}T_j.$$

复杂度

• 子任务 1：与完整状态数成正比。
• 子任务 2：$O(\pi(S)n+S)$ 时间，其中 $S=\sum |s_i|$。
• 满分算法：$O(S\log S)$ 时间，$O(S)$ 空间。

正确性证明

引理 1

把每个振荡串替换成最短循环节不改变粒子运动。

证明。 替换前后在每次访问时读到的字符序列完全相同，因此所有反向决策相同。 证毕。

引理 2

对固定质数 $p$，算法得到的 $e_0$ 是使整条链可行的最小初始指数。

证明。 到达第 $i$ 个振荡器前必须有 $e_{i-1}\ge v_p(a_i')$ 才能整除。扫描时若 不足，任何可行解都至少要补上该差值；补足后按比例式更新到 $e_i$。因此每次增加都必要， 最终值可行且最小。证毕。

定理

算法输出粒子位置的最小循环节。

证明。 由引理 1 可假定所有串均为最短周期。对每个质数应用引理 2，合并得到最小 正整数边界次数 $T_0$，比例链唯一确定其余 $T_i$。这些次数使所有振荡器状态同时复原， 且任何更小周期都会在某个质因子上违反最小性。每次跨越区间耗时一秒，往返产生因子 $2$，故周期正是 $2\sum T_i$。证毕。