哇哦二进制串 / Wowee Binary String

ID: 18515

传统题

2000ms

512MiB

难度: (无)

上传者:

标签>

combinatorics

strings

题目描述

给定一个只包含 0、1、? 的字符串 $s$ 。

首先，你需要把每个 ? 独立替换为 0 或 1。

之后，可以反复删除任意一个子串，只要这个子串中 1 的个数为偶数。删除后剩余部分会拼接起来。

求最终可能得到多少种不同的二进制串。答案对 $998244353$ 取模。

每个测试包含多组测试数据。

第一行包含整数 $t$ （ $1 \le t \le 100$ ）。

每组测试数据第一行包含整数 $n$ （ $1 \le n \le 3000$ ），表示字符串长度。

第二行包含一个长度为 $n$ 的未完成二进制串 $s$ 。

保证所有测试数据的 $n$ 之和不超过 $3000$ 。

对于每组测试数据，输出可以得到的不同二进制串数量，对 $998244353$ 取模。

7
1
?
5
?????
5
?1001
8
10010001
7
00??10?
7
?1?0?1?
16
0??000?00??1?1?0