← 返回题目列表

Codeforces · 1743/G

G. 反斐波那契切线

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

请注意,内存限制不正常。

让我们定义斐波那契字符串的序列如下:$$$f_0$$$ 为 0,$$$f_1$$$ 为 1,$$$f_i$$$ 为 $$$f_{i-1} + f_{i-2}$$$ for $$$i>1$$$($$$+$$$ 表示两个字符串的串联)。因此,例如,$$$f_2$$$ 为 10,$$$f_3$$$ 为 101,$$$f_4$$$ 为 10110。

对于给定的字符串 $$$s$$$,我们将 $$$g(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$$$。

示例

输入 #1

1
10110101

输出 #1

3

输入 #2

3
1111
1
0

输出 #2

2
3
3

输入 #3

6
10110101
100100001110
0000001100010001
1111
1001010100101010101001
000100000010101111

输出 #3

3
561
1466229
9887505
972227653
52128355