CF1896H2 Cyclic Hamming (Hard Version)

这是该问题的困难版本。两个版本的唯一区别在于 $k$ 的约束条件。只有在所有版本的问题都被解决后，你才能进行 hack。 在本题中，所有字符串均为 $0$ 下标。 对于两个长度为 $p$ 的字符串 $a$ 和 $b$，我们有如下定义： - $a$ 和 $b$ 的汉明距离，记作 $h(a, b)$，定义为满足 $0 \le i < p$ 且 $a_i \ne b_i$ 的位置 $i$ 的个数。 - 如果存在某个 $0 \leq k < p$，使得对于所有 $0 \le i < p$，都有 $b_{(i+k) \bmod p} = a_i$，则称 $b$ 是 $a$ 的循环移位。这里 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。 你将得到两个长度为 $2^{k+1}$ 的二进制字符串 $s$ 和 $t$。两个字符串中都可能包含缺失字符（用字符 '?' 表示）。你的任务是统计有多少种方法可以将两个字符串中的所有缺失字符替换为 '0' 或 '1'，使得： - 每个字符串 $s$ 和 $t$ 中恰好各有 $2^k$ 个字符 '0' 和 $2^k$ 个字符 '1'； - 对于 $t$ 的所有循环移位 $c$，都有 $h(s, c) \ge 2^k$。 由于答案可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。

输入的第一行包含一个整数 $k$（$1 \le k \le 12$）。 第二行输入长度为 $2^{k+1}$ 的字符串 $s$，仅包含字符 '0'、'1' 和 '?'。 第三行输入长度为 $2^{k+1}$ 的字符串 $t$，仅包含字符 '0'、'1' 和 '?'。 保证两个字符串 $s$ 和 $t$ 中 '0' 或 '1' 的数量都不超过 $2^k$。

输出一个整数，表示满足条件的方案数，对 $998\,244\,353$ 取模。

在第一个样例中，可以验证对于 $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}$。 由 ChatGPT 4.1 翻译