#P17722. [2026年福建省队集训]基础集合幂级数练习题

[2026年福建省队集训]基础集合幂级数练习题

题目描述

小 ε\varepsilon 最近在学习集合幂级数。为了巩固知识,她找到了一道有趣的练习题,想和同学们分享一下。

给定正整数 nn,对于 {0,1,⋯ ,n−1}\{0,1,\cdots,n-1\} 的每个非空子集,已经分别确定了它是否可以作为叶子集合,以及是否可以作为根集合。

现在考虑一棵有根树。树上每个点都写有一个 {0,1,⋯ ,n−1}\{0,1,\cdots,n-1\} 的非空子集作为标号,并且需要满足以下条件:

  • 每个点的儿子个数为 00 或 22;
  • 若一个点没有儿子,则它的标号必须可以作为叶子集合;
  • 若一个点有两个儿子,设这个点的标号为 AA,两个儿子的标号分别为 B,CB,C,则需要满足 B∪C=AB\cup C=A 且 B∩C=∅B\cap C=\varnothing;
  • 根节点的标号必须可以作为根集合。

特别地,对于有两个儿子的点,这两个儿子的顺序不作区分。

请求出满足条件的有根树数量,对 998244353998244353 取模。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0c=0。

对于每组测试数据:

  • 第一行一个正整数 nn;
  • 第二行一个长度为 2n2^n 的 01\texttt{01} 串 LL,描述哪些集合可以作为叶子集合;
  • 第三行一个长度为 2n2^n 的 01\texttt{01} 串 RR,描述哪些集合可以作为根集合。

对于一个子集 A⊆{0,1,⋯ ,n−1}A\subseteq\{0,1,\cdots,n-1\},记 mask(A)=∑a∈A2amask(A)=\sum_{a\in A}2^a。LL 的第 mask(A)+1mask(A)+1 个字符为 1\texttt{1} 当且仅当 AA 可以作为叶子集合;RR 的第 mask(A)+1mask(A)+1 个字符为 1\texttt{1} 当且仅当 AA 可以作为根集合。

保证两个字符串的第一个字符均为 0\texttt{0}。

输出格式

对于每组测试数据输出一行一个非负整数,表示答案对 998244353998244353 取模后的结果。

样例

样例输入 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\},\{1\},\{0,1\},\{0,2\},\{1,2\},\{0,1,2\},可以作为根集合的集合为 {0,2},{0,1,2}\{0,2\},\{0,1,2\}。

满足条件的树共有 44 棵:

  • 根标号为 {0,2}\{0,2\} 的单点树;
  • 根标号为 {0,1,2}\{0,1,2\} 的单点树;
  • 根标号为 {0,1,2}\{0,1,2\},两个儿子标号为 {0},{1,2}\{0\},\{1,2\} 的树;
  • 根标号为 {0,1,2}\{0,1,2\},两个儿子标号为 {1},{0,2}\{1\},\{0,2\} 的树。

数据范围与提示

对于所有测试数据:

  • T≤10T \le 10;
  • 1≤n≤201 \le n \le 20;
  • L,RL,R 均为长度 2n2^n 的 01\texttt{01} 串,且第一个字符均为 0\texttt{0}。
测试点编号 n≤n\le 特殊性质
1∼21\sim 2 55 无
3∼53\sim 5 88
6∼86\sim 8 1212
9∼119\sim 11 1616
12∼1312\sim 13 2020 A
14∼1514\sim 15 B
16∼1716\sim 17 C
18∼2018\sim 20 1818 无
21∼2521\sim 25 2020
  • 特殊性质 A:一个集合可以作为叶子集合当且仅当它的大小为 11;
  • 特殊性质 B:恰好有一个集合可以作为根集合;
  • 特殊性质 C:每个非空集合都可以作为叶子集合。

【提示】

本题输入文件较大,请使用较为快速的输入输出方式。