CF1778D Flexible String Revisit

给定两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。每一步，你可以对字符串 $a$ 进行如下操作： - 随机等概率选择一个下标 $i$（$1 \leq i \leq n$），将 $a_i$ 反转。如果 $a_i$ 是 $0$，则变为 $1$；如果 $a_i$ 是 $1$，则变为 $0$。 问：期望需要多少次操作，才能使得 $a$ 和 $b$ 第一次完全相等？ 二进制字符串是指每个字符都是 $0$ 或 $1$ 的字符串。

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^6$），表示字符串的长度。 第二行包含一个长度为 $n$ 的二进制字符串 $a$。 第三行包含一个长度为 $n$ 的二进制字符串 $b$。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一行，表示期望的操作次数，对 $998\,244\,353$ 取模。 形式化地，设 $M = 998\,244\,353$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

在第一个测试用例中，随机选择下标 $1$ 并翻转 $a_1$，操作后 $a$ 和 $b$ 相等。期望操作次数为 $1$。 在第二个测试用例中，$a$ 和 $b$ 已经相等，所以期望操作次数为 $0$。 第三和第四个测试用例的期望操作次数分别为 $\frac{56}{3}$ 和 $\frac{125}{3}$。 由 ChatGPT 4.1 翻译