CF1743G Antifibonacci Cut

注意，本题的内存限制不同寻常。 我们定义斐波那契字符串序列如下：$f_0$ 为 0，$f_1$ 为 1，$f_i$ 为 $f_{i-1} + f_{i-2}$，其中 $i > 1$（$+$ 表示两个字符串的拼接）。例如，$f_2$ 为 10，$f_3$ 为 101，$f_4$ 为 10110。 对于给定的字符串 $s$，我们定义 $g(s)$ 为将 $s$ 切分成若干个（任意数量，甚至可以只切成一个）字符串的方案数，使得这些字符串中没有一个是斐波那契字符串。例如，若 $s$ 为 10110101，$g(s) = 3$，因为有三种切分方式： - 101101 $+$ 01； - 1011 $+$ 0101； - 1011 $+$ 01 $+$ 01。 给定一组字符串 $s_1, s_2, \dots, s_n$，请计算 $g(s_1), g(s_1 + s_2), \dots, g(s_1 + s_2 + \ldots + s_n)$。由于答案可能很大，请对 $998244353$ 取模后输出。

输入的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^3$）。 接下来有 $n$ 行，第 $i$ 行包含字符串 $s_i$（$1 \le |s_i| \le 10^3$），字符串仅由字符 0 和/或 1 组成。

输出 $n$ 个整数，第 $i$ 个整数表示 $g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$。

由 ChatGPT 4.1 翻译