← 返回题目列表

AtCoder · xmascon20_h

H. 层次系统发育

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

配点 : 100 点

进行生物学研究的鳗鱼,想要计算某些生物分类的系统树数量。在鳗鱼的研究中,已经列出了一些可以被视为不再细分的物种集合,以及作为系统树制作对象的集合。当然,鳗鱼并不擅长计数也不会影响它,但今天由于紧急情况,它必须非常快速地进行计数。

問題文

正整数 N 。\{0, \ldots, N - 1\} 的非空子集各自,“是否适合作为叶子”以及“是否适合作为根”已被确定。

在带根树的各顶点上, \{0, \ldots, N - 1\} 的非空子集 1 个被写作标签,且满足以下所有条件的数量除以 998244353 取余数:

  • 每个顶点的子节点为 0 件或 2 。
  • 子节点为 0 个顶点的标签适合作为叶子。
  • 子节点为 2 个顶点满足以下条件:该顶点的标签为 A,子节点的标签为 B, C 时,B \cup C = A 和 B \cap C = \emptyset.
  • 根的标签适合作为根。

但是,对于有 2 个子节点的顶点,它们的顺序不区分。

制約

  • 1 \le N \le 21.

入力

输入是按以下格式从标准输入给出的。

N
L
R

L 是 您也可以写 0 和 按字典顺序比较 1 组成的长度 2^N 是一个字符串,每个 A \subseteq \{0, \ldots, N - 1\} , 定义\left(1 + \sum_{a\in A} 2^a\right) 第一个字符是 A 是 在是否适合作为叶子时, 1,否则 0 。但是,1 个字符(开头)必须满足条件。 0 是。

R 是 您也可以写 0 和 按字典顺序比较 1 组成的长度 2^N 是一个字符串,每个 A \subseteq \{0, \ldots, N - 1\} , 定义\left(1 + \sum_{a\in A} 2^a\right) 第一个字符是 A 是 在是否适合作为根时, 1,否则 0 。但是,1 个字符(开头)必须满足条件。 0 是。

出力

满足条件的标记根树的数量为 998244353 后的余数。 对于


入力例 1

3
01110111
00000101

出力例 1

4

。 在这个例子中,适合作为叶子的集合有 \{0\}, \{1\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\} 可以得到第 6 个,适合作为根的集合有 \{0, 2\}, \{0, 1, 2\} 可以得到第 2 个。满足条件的标记根树如下 4 个:

  • 根的标签是 \{0, 2\} 是 1 顶点树 在
  • 根的标签是 \{0, 1, 2\} 是 1 顶点树 在
  • 根的标签是 \{0, 1, 2\} 并且,其子节点的标签是 \{0\}, \{1, 2\} 是 3 顶点树 在
  • 根的标签是 \{0, 1, 2\} 并且,其子节点的标签是 \{1\}, \{0, 2\} 是 3 顶点树 在

入力例 2

5
00000001000101100001011001101000
00000000000000010000000100010111

出力例 2

0

入力例 3

6
0111001111111111111111101111111111111111111110111111111111111110
0111001111111111111111111111111111110111111111111001000000010001

出力例 3

2020