Codeforces Round 865 (Div. 1) |
---|
Закончено |
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$$$) — количество излучателей.
$$$i$$$-я из следующих $$$n$$$ строк содержит бинарную строку $$$s_i$$$ ($$$1\le\left|s_i\right|\le10^6$$$) — бинарная строка, содержащая только символы $$$\texttt{0}$$$ и $$$\texttt{1}$$$, описывающая излучатель на позиции $$$i$$$.
Гарантируется, что сумма $$$|s_i|$$$ не превосходит $$$10^6$$$.
Выведите единственное целое число — длину цикла движения частицы, взятую по модулю $$$998244353$$$.
1 00
4
2 01 010
16
4 0101 000 1 01
12
4 01010 0001 11 0001
120
В первом примере единственный излучатель на позиции $$$1$$$ всегда имеет состояние $$$\texttt{0}$$$. В моменты времени $$$0,1,2,3$$$ позиции частицы равны $$$0,1,2,1$$$ соответственно. Затем те же позиции будут повторяться, поэтому $$$c=4$$$.
Анимация для второго примера: здесь или более плавная анимация.
Название |
---|