Antifibonacci Cut

题意翻译

定义 $01$ 串 $f$ 为斐波那契串，其中 $f_1=0,f_2 = 1,f_{n}=f_{n-1}+f_{n-2}$，其中 $+$ 代表拼接。再定义 $g(s)$ 表示把 $s$ 分割成若干个子串，并且没有任何子串是斐波那契串的方案数。现给出 $n(n\leq 3000)$ 个 $01$ 串 $s_1,s_2,...,s_n$（$|s_i|\leq 1000$），要求对于每个 $i$，计算 $g(s_1+s_2+...+s_i)\pmod {998244353}$。**内存限制为 $4\text M$**。

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

Print $ n $ integers, where the $ i $ -th integer is $ 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

**题目大意：**
定义一个斐波那契字符串序列 $ f $，其中 $ f_0 = 0 $，$ f_1 = 1 $，对于 $ i > 1 $，$ f_i = f_{i-1} + f_{i-2} $（这里的加号代表字符串的拼接）。例如，$ 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 3000 $）。接下来 $ n $ 行，每行包含一个字符串 $ s_i $（$ 1 \le |s_i| \le 1000 $），字符串由字符 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
```**题目大意：** 定义一个斐波那契字符串序列 $ f $，其中 $ f_0 = 0 $，$ f_1 = 1 $，对于 $ i > 1 $，$ f_i = f_{i-1} + f_{i-2} $（这里的加号代表字符串的拼接）。例如，$ 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 3000 $）。接下来 $ n $ 行，每行包含一个字符串 $ s_i $（$ 1 \le |s_i| \le 1000 $），字符串由字符 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 ```