题目描述
小 ε 最近在学习集合幂级数。为了巩固知识,她找到了一道有趣的练习题,想和同学们分享一下。
给定正整数 n,对于 {0,1,⋯,n−1} 的每个非空子集,已经分别确定了它是否可以作为叶子集合,以及是否可以作为根集合。
现在考虑一棵有根树。树上每个点都写有一个 {0,1,⋯,n−1} 的非空子集作为标号,并且需要满足以下条件:
- 每个点的儿子个数为 0 或 2;
- 若一个点没有儿子,则它的标号必须可以作为叶子集合;
- 若一个点有两个儿子,设这个点的标号为 A,两个儿子的标号分别为 B,C,则需要满足 B∪C=A 且 B∩C=∅;
- 根节点的标号必须可以作为根集合。
特别地,对于有两个儿子的点,这两个儿子的顺序不作区分。
请求出满足条件的有根树数量,对 998244353 取模。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0。
对于每组测试数据:
- 第一行一个正整数 n;
- 第二行一个长度为 2n 的 01 串 L,描述哪些集合可以作为叶子集合;
- 第三行一个长度为 2n 的 01 串 R,描述哪些集合可以作为根集合。
对于一个子集 A⊆{0,1,⋯,n−1},记 mask(A)=∑a∈A2a。L 的第 mask(A)+1 个字符为 1 当且仅当 A 可以作为叶子集合;R 的第 mask(A)+1 个字符为 1 当且仅当 A 可以作为根集合。
保证两个字符串的第一个字符均为 0。
输出格式
对于每组测试数据输出一行一个非负整数,表示答案对 998244353 取模后的结果。
样例
样例输入 1
0 2
3
01110111
00000101
2
0111
0001
样例输出 1
4
2
样例解释 1
对于第一组数据,可以作为叶子集合的集合为 {0},{1},{0,1},{0,2},{1,2},{0,1,2},可以作为根集合的集合为 {0,2},{0,1,2}。
满足条件的树共有 4 棵:
- 根标号为 {0,2} 的单点树;
- 根标号为 {0,1,2} 的单点树;
- 根标号为 {0,1,2},两个儿子标号为 {0},{1,2} 的树;
- 根标号为 {0,1,2},两个儿子标号为 {1},{0,2} 的树。
数据范围与提示
对于所有测试数据:
- T≤10;
- 1≤n≤20;
- L,R 均为长度 2n 的 01 串,且第一个字符均为 0。
| 测试点编号 |
n≤ |
特殊性质 |
| 1∼2 |
5 |
无 |
| 3∼5 |
8 |
| 6∼8 |
12 |
| 9∼11 |
16 |
| 12∼13 |
20 |
A |
| 14∼15 |
B |
| 16∼17 |
C |
| 18∼20 |
18 |
无 |
| 21∼25 |
20 |
- 特殊性质 A:一个集合可以作为叶子集合当且仅当它的大小为 1;
- 特殊性质 B:恰好有一个集合可以作为根集合;
- 特殊性质 C:每个非空集合都可以作为叶子集合。
【提示】
本题输入文件较大,请使用较为快速的输入输出方式。