CF1815E Bosco and Particle

Bosco 正在研究粒子的行为。他决定研究一种被称为“四一二”粒子的特殊行为。他的实验如下： 有一条长度为 $n+1$ 的直线，最顶端为位置 $0$，最底端为位置 $n+1$。粒子初始时刻（$t=0$）位于位置 $0$，并朝向下方运动。粒子的速度为每秒 $1$ 个单位。在位置 $1,2,\ldots,n$ 各有一个振荡器。 每个振荡器由一个二进制字符串描述。每个振荡器的初始状态为其二进制字符串的第一个字符。当粒子撞击某个振荡器时，如果该振荡器当前状态为 $1$，粒子会反向运动；如果当前状态为 $0$，粒子会继续保持原方向运动。随后，该振荡器的状态会切换到下一个（最后一个状态的下一个定义为第一个状态）。此外，每当粒子在 $t>0$ 时到达位置 $0$ 或 $n+1$，粒子都会反向运动。 Bosco 想知道粒子运动的循环节长度。循环节长度定义为最小的 $c$，使得对于任意 $t\ge 0$，粒子在时刻 $t$ 和 $t+c$ 的位置相同。可以证明这样的 $c$ 总是存在。由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

第一行包含一个整数 $n$（$1\le n\le 10^6$），表示振荡器的数量。 接下来的 $n$ 行中，第 $i$ 行包含一个二进制字符串 $s_i$（$1\le |s_i| \le 10^6$），仅包含字符 $0$ 和 $1$，描述了第 $i$ 个位置的振荡器。 保证所有 $|s_i|$ 的总和不超过 $10^6$。

输出一个整数，表示粒子运动的循环节长度，对 $998244353$ 取模后的结果。

在第一个样例中，唯一的振荡器始终处于状态 $0$。在时刻 $0,1,2,3$，粒子的位置分别为 $0,1,2,1$。之后位置会重复，因此 $c=4$。 第二个样例的动画见：[这里](https://u.cubeupload.com/culver0412/GJ5PNy.png) 或 [更流畅的动画](https://i.imgur.com/X35t71G.gif)。 由 ChatGPT 4.1 翻译