← 返回题目列表

Codeforces · 1815/E

E. 博斯科和粒子

中文机器翻译题面 查看原题

Bosco 正在研究粒子的行为。他决定研究所谓的“四一二”粒子的奇特行为。他执行以下操作:

有一条长度为 $$$n+1$$$ 的线,其中最上面的点是位置 $$$0$$$,最下面的点是位置 $$$n+1$$$。粒子最初(在时间 $$$t=0$$$ 时)位于位置 $$$0$$$ 并向下移动。粒子以每秒 $$$1$$$ 单位的速度移动。在 $$$1,2,\ldots,n$$$ 位置有 $$$n$$$ 振荡器。

每个振荡器都可以用二进制字符串来描述。每个振荡器的初始状态是其二进制字符串的第一个字符。当粒子撞击振荡器时,如果其当前状态为 $$$\texttt{1}$$$,则粒子会反转其方向;如果其当前状态为 $$$\texttt{0}$$$,则继续沿相同方向移动,并且该振荡器将移动到下一个状态(最后一个状态的下一个状态定义为第一个状态)。此外,当粒子位于 $$$0$$$ 位置或 $$$n+1$$$ 且时间 $$$t > 0$$$ 时,粒子始终会反转其方向。

Bosco 想知道粒子运动的周期长度。循环长度定义为 $$$c$$$ 的最小值,使得对于任何时间 $$$t \ge 0$$$,粒子在时间 $$$t$$$ 的位置与粒子在时间 $$$t+c$$$ 的位置相同。可以证明这样的值$$$c$$$总是存在的。当他意识到答案可能太大时,他要求您输出对 $$$998244353$$$ 取模的答案。

输入

第一行包含一个整数 $$$n$$$ ($$$1\le n\le10^6$$$) — 振荡器的数量。

下一个 $$$n$$$ 行的第 $$$i$$$ 包含一个二进制字符串 $$$s_i$$$ ($$$1\le\left|s_i\right|\le10^6$$$) — 二进制字符串,仅包含字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$,描述位置处的振荡器$$$我$$$。

保证所有$$$|s_i|$$$的总和不超过$$$10^6$$$。

输出

输出一个整数 - 粒子运动的周期长度,以 $$$998244353$$$ 为模。

示例

输入 #1

1
00

输出 #1

4

输入 #2

2
01
010

输出 #2

16

输入 #3

4
0101
000
1
01

输出 #3

12

输入#4

4
01010
0001
11
0001

输出#4

120

注意

在第一个样本中,位于 $$$1$$$ 位置的唯一振荡器始终具有状态 $$$\texttt{0}$$$。在$$$0,1,2,3$$$时刻,粒子的位置分别为$$$0,1,2,1$$$。那么相同的位置将会重复,所以$$$c=4$$$。

第二个示例的动画:此处或更平滑的动画。