CF1815E Bosco and Particle 题解 / 周期引理学习笔记

zrl123456 · 2025-12-16 19:25:19 · 题解

:::::info[题目基本信息] 考察：Ad-hoc，KMP，筛法，逆元（3100）。
题目简介：
给定字符串序列 \{s_n\}，由 \texttt 0 和 \texttt 1 组成，同时 s_0=s_{n+1}=\texttt{1}。你现在有一个数轴，上面在 0 到 n+1 的位置各有一个机关，分别对应 s[0,n+1]（a[l,r] 表示 a_l,a_{l+1},\dots,a_r），初始时机关状态均为所对应字符串的第一个字符，现在你初始位于位置 0，面向正方向，现在每过一时刻你都会进行：

• 向自己面向的方向移动一个单位长度。
• 若所位于的位置的机关状态为 \texttt 1，那么回头。
• 将所位于的位置的机关状态调整为下一个字符的状态（最后一个字符的下一个字符是第一个字符）。

现在求最小周期 c（使得对于任意时刻 t，时刻 t 位于的位置和时刻 t+c 位于的位置均相同）对 998244353 取模的结果。
数据范围：

• 1\le n\le 10^6
• \forall i\in[1,n],1\le|s_i|\le 10^6
• \sum|s_i|\le 10^6

  ::::: 首先你这个 \{s_n\} 里的每一个字符串都只需要保留最小整周期（满足 d\mid|s| 且 d 是 s 的周期的最小 d）长度，这样容易发现开始循环就是回到初始状态（即位于位置 0 且所有机关状态均为对应字符串的第一个字符），那么这个最小整周期其实是好求的，因为有定理：

• 若一个字符串的最小周期不是该字符串的整周期，那么该字符串的最小整周期是 |s|，否则就是这个周期。 :::::success[证明] 后半句话是显然的，重点在前半句话。
  注意到在最小整周期 d 不等于 |s| 时，必须有 d\le\frac{|s|}{2}，此时若最小整周期不是最小周期，那么两者的 \gcd 就是更小的整周期（周期引理），矛盾。
• 周期引理：若字符串 s 有两周期 p,q，那么设 g=\gcd(p,q)，若 p+q\le n+g，则 g 也是 s 的周期。
  证明：唉感觉这种感性理解很好理解的定理的证明不太适合摆在这个题解里啊，就放在这吧。
  ::::: 好的那么我们先考虑 n=1 怎么做，这个是简单的，你可以直接暴力模拟一下，容易直接算出周期。
  考虑怎么推广，注意到若对于每一个 s_i 单独做一遍 n=1 后得到了 0\rightarrow 1 的次数（设为 a_i）和 1\rightarrow 2 的次数（设为 b_i），同时设本题的模拟过程 i\rightarrow i+1 的次数为 f_i，那么模拟过程回到了初始状态当且仅当 \forall i\in[1,n],f_{i-1}:f_i=a_i:b_i。
  :::::success[证明] 如果不满足 \forall i\in[1,n],f_{i-1}:f_i=a_i:b_i，那么找到这个不满足的 i 设为 id，那么 id 一定没有还原会初始状态，整个模拟过程也没有。
  否则，每一个 i 容易发现都回到了初始状态，同时保证了此时你位于每一个 i 的左边（即最左边）。
  ::::: 那么我们最小的周期 \displaystyle c=2\sum_{i=0}^nf_i，此时我们只需求出 \{f_n\} 的最小整数解即可。
  这个是简单的，将所有的 f_i 表示成 \dfrac{af_0}{b} 的形式（a,b\in\Z,a\,\bot\, b），然后求一下所有 b 的 \text{lcm} 即可，由于 b 可能很大所以我们可以跑一遍欧拉筛然后对于每个质数开桶维护历史最大值即可。
  这样我们就解决了此题。

时间复杂度为 \Theta(\sum|s|+n(\log p+\log\sum|s|))，空间复杂度为 \Theta(\sum|s|+n)。

code