[Solution] Antifibonacci Cut Codeforces Solution

G. Antifibonacci Cut

time limit per test

12 seconds

memory limit per test

4 megabytes

input

standard input

output

standard output

Note that the memory limit is unusual.

Let's define the sequence of Fibonacci strings as follows: 𝑓0$f_0$ is 0, 𝑓1$f_1$ is 1, 𝑓𝑖$f_i$ is 𝑓𝑖−1+𝑓𝑖−2$f_{i-1}+f_{i-2}$ for 𝑖>1$i>1$ (+$+$ denotes the concatenation of two strings). So, for example, 𝑓2$f_2$ is 10, 𝑓3$f_3$ is 101, 𝑓4$f_4$ is 10110.

For a given string 𝑠$s$, let's define 𝑔(𝑠)$g(s)$ as the number of ways to cut it into several (any number, possibly even just one) strings such that none of these strings are Fibonacci strings. For example, if 𝑠$s$ is 10110101, 𝑔(𝑠)=3$g(s)=3$ since there are three ways to cut it:

• 101101 +$+$ 01;
• 1011 +$+$ 0101;
• 1011 +$+$ 01 +$+$ 01.

You are given a sequence of strings 𝑠1,𝑠2,…,𝑠𝑛$s_1,s_2,\dots ,s_n$. Calculate 𝑔(𝑠1),𝑔(𝑠1+𝑠2),…,𝑔(𝑠1+𝑠2+…+𝑠𝑛)$g(s_1),g(s_1+s_2),\dots ,g(s_1+s_2+\dots +s_n)$. Since these values can be huge, print them modulo 998244353$998244353$.

Input

The first line of the input contains one integer 𝑛$n$ (1≤𝑛≤3⋅103$1\le n\le 3\cdot {10}^3$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Then, 𝑛$n$ lines follow. The 𝑖$i$-th line contains the string 𝑠𝑖$s_i$ (1≤|𝑠𝑖|≤103$1\le |s_i|\le {10}^3$), consisting of characters 0 and/or 1.

Output

Print 𝑛$n$ integers, where the 𝑖$i$-th integer is 𝑔(𝑠1+𝑠2+…+𝑠𝑖)mod998244353$g(s_1+s_2+\dots +s_i)mod998244353$.