AT_utpc2022_n.01 String Game

给定一个整数 $N$，以及一个仅由 0 和 1 组成的、长度为 $N$ 的字符串 $T$。有一个仅由 0 和 1 组成的、长度为 $2N$ 的字符串 $S = s_1 s_2 \ldots s_{2N}$。Alice 和 Bob 使用 $S$ 与 $T$ 进行游戏。两人轮流操作，从 Alice 开始，直到 $S$ 的所有字符都被标记完为止：

• 挑选一个 $1 \le i \le 2N$ 且 $s_i$ 位置还未被标记的下标 $i$。然后：
  • 若是 Alice 的回合，将该位标记为 o。
  • 若是 Bob 的回合，将该位标记为 x。

游戏结束后，只读取所有被标记为 o 的下标，按从左到右顺序拼接，组成一个长度为 $N$ 的字符串。如果这个字符串在字典序上大于等于 $T$，则 Alice 获胜；否则 Bob 获胜。

所有可能作为初始字符串 $S$ 的情况一共有 $2^{2N}$ 种。请计算，在两人都采取最优策略、各自努力争取胜利的情况下，Alice 能获胜的 $S$ 有多少种。将答案对 $998244353$ 取模后输出。

输入以以下格式通过标准输入给出。

$N$ $T$

输出一行，表示答案。

样例解释 1

所有由 0 或 1 组成的长度为 $2$ 的字符串都符合。

样例解释 2

仅有 01、10、11 这 $3$ 种情况符合条件。

约束条件

• $N$ 是整数
• $1 \leq N \leq 2 \times 10^5$
• $T$ 是仅由 0、1 组成的长度为 $N$ 的字符串。

由 ChatGPT 5 翻译