← 返回题目列表

Codeforces · 1896/H1

H1. 循环汉明(简单版)

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

这是问题的简单版本。两个版本之间的唯一区别是对 $$$k$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

在此语句中,所有字符串均以 $$$0$$$ 为索引。

对于两个长度相同的字符串 $$$a$$$, $$$b$$$ $$$p$$$,我们定义以下定义:

- $$$a$$$ 和 $$$b$$$ 之间的汉明距离,表示为 $$$h(a, b)$$$,定义为 $$$i$$$ 的位置数,使得 $$$0 \le i < p$$$ 且 $$$a_i \ne b_i$$$。
- $$$b$$$ 是 $$$a$$$ 的循环移位,如果存在一些 $$$0 \leq k < p$$$ 使得 $$$b_{(i+k) \bmod p} = a_i$$$ 对于所有 $$$0 \le i < p$$$。这里 $$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 的余数。

给你两个二进制字符串 $$$s$$$ 和 $$$t$$$,每个长度为 $$$2^{k+1}$$$。两个字符串都可能包含缺失字符(用字符“?”表示)。您的任务是计算用字符“0”或“1”替换两个字符串中缺失字符的方法数量,以便:

- 每个字符串 $$$s$$$ 和 $$$t$$$ 恰好包含每个字符“0”和“1”的 $$$2^k$$$ 出现次数
- $$$h(s, c) \ge 2^k$$$ 对于所有字符串 $$$c$$$ 来说是 $$$t$$$ 的循环移位。

由于结果可能非常大,因此您应该打印对 $$$998\,244\,353$$$ 取模的值。

输入

输入的第一行包含一个整数 $$$k$$$ ($$$1 \le k \le 7$$$)。

输入的第二行包含大小为 $$$2^{k+1}$$$ 的字符串 $$$s$$$,由字符“0”、“1”和“?”组成。

输入的第三行包含大小为 $$$2^{k+1}$$$ 的字符串 $$$t$$$,由字符“0”、“1”和“?”组成。

保证字符串 $$$s$$$ 和 $$$t$$$ 包含不超过 $$$2^k$$$ 字符“0”或“1”。

输出

打印一个整数 - 问题的答案以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

1
0011
0101

输出 #1

1

输入 #2

1
0011
0110

输出 #2

0

输入 #3

1
0??1
01??

输出 #3

2

输入#4

2
000?????
01010101

输出#4

3

输入 #5

2
0???????
1???????

输出 #5

68

输入 #6

5
0101010101010101010101010101010101010101010101010101010101010101
????????????????????????????????????????????????????????????????

输出 #6

935297567

注意

在第一个示例中,我们可以检查 $$$t$$$ 的所有循环移位 $$$c$$$ 的条件 $$$h(s, c) \ge 2^k$$$ 是否得到满足。特别是:

- 对于 $$$c = \mathtt{0101}$$$, $$$h(s, c) = h(\mathtt{0110}, \mathtt{0101}) = 2 \ge 2^1$$$;
- 对于 $$$c = \mathtt{1010}$$$, $$$h(s, c) = h(\mathtt{0110}, \mathtt{1010}) = 2 \ge 2^1$$$。

在第二个示例中,存在 $$$t$$$ 的循环移位 $$$c$$$,使得 $$$h(s, c) < 2^k$$$ (特别是,$$$c = \mathtt{0011}$$$,并且 $$$h(s, c) = h(\mathtt{0011}, \mathtt{0011}) = 0$$$)。

在第三个示例中,有 $$$2$$$ 可能的方法来恢复丢失的字符:

- $$$s = \mathtt{0101}$$$, $$$t = \mathtt{0110}$$$;
- $$$s = \mathtt{0011}$$$,$$$t = \mathtt{0101}$$$。

在第四个示例中,有 $$$3$$$ 可能的方法来恢复丢失的字符:

- $$$s = \mathtt{00011110}$$$, $$$t = \mathtt{01010101}$$$;
- $$$s = \mathtt{00011011}$$$, $$$t = \mathtt{01010101}$$$;
- $$$s = \mathtt{00001111}$$$,$$$t = \mathtt{01010101}$$$。