CF1778D.Flexible String Revisit

You are given two binary strings $a$ and $b$ of length $n$. In each move, the string $a$ is modified in the following way.

• An index $i$ ($1 \leq i \leq n$) is chosen uniformly at random. The character $a_i$ will be flipped. That is, if $a_i$ is $0$, it becomes $1$, and if $a_i$ is $1$, it becomes $0$.

What is the expected number of moves required to make both strings equal for the first time?

A binary string is a string, in which the character is either $\tt{0}$ or $\tt{1}$.

给你两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。在每一步操作中，字符串 $a$ 按如下方式被修改：

• 均匀随机地选择一个下标 $i$（$1 \leq i \leq n$），并将字符 $a_i$ 翻转：即若 $a_i$ 为 $\tt{0}$，则变为 $\tt{1}$；若 $a_i$ 为 $\tt{1}$，则变为 $\tt{0}$。

问：使两个字符串首次相等所需的期望操作次数是多少？

二进制字符串是指仅由字符 $\tt{0}$ 或 $\tt{1}$ 组成的字符串。

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^6$) — the length of the strings.

The second line of each test case contains the binary string $a$ of length $n$.

The third line of each test case contains the binary string $b$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）—— 表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）—— 表示字符串的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $a$。

每个测试用例的第三行包含一个长度为 $n$ 的二进制字符串 $b$。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

For each test case, output a single line containing the expected number of moves modulo $998\,244\,353$.

Formally, let $M = 998\,244\,353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对于每个测试用例，输出一行，包含期望移动次数对 $998\,244\,353$ 取模的结果。

形式化地，令 $M = 998\,244\,353$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，请输出满足 $0 \le x \lt M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first test case, index $1$ is chosen randomly and $a_1$ is flipped. After the move, the strings $a$ and $b$ are equal. The expected number of moves is $1$.

The strings $a$ and $b$ are already equal in the second test case. So, the expected number of moves is $0$.

The expected number of moves for the third and fourth test cases are $\frac{56}{3}$ and $\frac{125}{3}$ respectively.

在第一个测试用例中，随机选择索引 $1$ 并翻转 $a_1$。操作后，字符串 $a$ 和 $b$ 相等。期望操作次数为 $1$。

在第二个测试用例中，字符串 $a$ 和 $b$ 已经相等，因此期望操作次数为 $0$。

第三个和第四个测试用例的期望操作次数分别为 $\frac{56}{3}$ 和 $\frac{125}{3}$。