Antifibonacci Cut
Contest: Educational Codeforces Round 137 (Rated for Div. 2)
Difficulty rating: 3000
Tags: bitmasks, combinatorics, constructive algorithms, data structures, dp, hashing, math

Note that the memory limit is unusual.

Let's define the sequence of Fibonacci strings as follows: $$$f_0$$$ is 0, $$$f_1$$$ is 1, $$$f_i$$$ is $$$f_{i-1} + f_{i-2}$$$ for $$$i>1$$$ ($$$+$$$ denotes the concatenation of two strings). So, for example, $$$f_2$$$ is 10, $$$f_3$$$ is 101, $$$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, $$$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 $$$s_1, s_2, \dots, s_n$$$. Calculate $$$g(s_1), g(s_1 + s_2), \dots, g(s_1 + s_2 + \ldots + s_n)$$$. Since these values can be huge, print them modulo $$$998244353$$$.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^3$$$).

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

Output format:
Print $$$n$$$ integers, where the $$$i$$$-th integer is $$$g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$$$.

Constraints:
Time limit: 12.0 s
Memory limit: 4.0 MB

Example input:
1
10110101

Example output:
3

Example input:
3
1111
1
0

Example output:
2
3
3

Editorial:
The first idea that comes to mind is running some sort of dynamic programming: $$$dp_i$$$ — the number of ways to cut the string consisting of the first $$$i$$$ characters. When we calculate $$$dp_i$$$, we need to take the sum of the previous values of $$$dp$$$, and then subtract $$$dp_j$$$ for every $$$j$$$ such that the string from the $$$j$$$-th character (inclusive) to the $$$i$$$-th character (non-inclusive) is a Fibonacci string. Unfortunately, there are two main issues with this solution: firstly, we cannot store the array $$$dp$$$ in memory; and secondly, we have to search for the Fibonacci strings ending in a certain index quickly (something like Aho-Corasick could work with a less strict memory limit, but right now we cannot use it).
We will try to resolve both of these issues with the following approach: while we process the characters, we will maintain the list of tuples $$$(j, dp_j)$$$ such that the string from the $$$j$$$-th character to the current one is a prefix of some Fibonacci string. How do we maintain them?
Every Fibonacci string $$$f_i$$$ (except for $$$f_0$$$) is a prefix of $$$f_{i+1}$$$. So, all Fibonacci strings we are interested in (except for $$$f_0$$$ again) are prefixes of the same long Fibonacci string. Suppose a tuple $$$(j, dp_j)$$$ represents some index $$$j$$$ such that the string from the $$$j$$$-th character to the current one is a prefix of that long Fibonacci string. Each time we append a character, we filter this list of tuples by trying to check if this new character matches the next character in the prefix (if it does not, the tuple is discarded). For the tuples that represent the prefixes equal to Fibonacci strings, we need to subtract the value of $$$dp_j$$$ from the new $$$dp$$$ value we are trying to calculate (checking if a prefix is a Fibonacci string is easy, we just need to check its length). How do we check that if we add a character 1 or 0, it is still a prefix? There are two ways to do this:
• either generate the first $$$3 \cdot 10^6$$$ characters of the long Fibonacci string;
• or represent the current prefix as the sum of Fibonacci strings $$$f_{i_1} + f_{i_2} + \dots + f_{i_k}$$$ such that for every $$$j \in [1, k - 1]$$$, the condition $$$f_{i_j} > f_{i_{j+1}} + 1$$$ holds (i. e. the Fibonacci strings we split the current prefix into are arranged in descending order, and there is no pair of equal or adjacent (by index) Fibonacci strings in the split). This representation is very similar to writing an integer in Zeckendorf system. The next character in the prefix depends on whether $$$f_1$$$ belongs to this split: if it belongs, it is the last string in the split, so we need to append 0 to transform $$$f_1$$$ into $$$f_2$$$; otherwise, we need to append 1.
Okay, so now we can solve the problem in $$$O(NM)$$$ time (where $$$N$$$ is the total length of the strings in the input, and $$$M$$$ is the size of the list of tuples $$$(j, dp_j)$$$ we discussed earlier). This actually works since it looks like the size of the list of tuples is bounded as $$$O(\log N)$$$. Unfortunately, we don't have a strict mathematical proof of this; we checked this by brute force with $$$N$$$ up to $$$3 \cdot 10^6$$$, so it definitely works under the constraints of the problem.