Flexible String Revisit
Contest: Codeforces Round 848 (Div. 2)
Difficulty rating: 2100
Tags: combinatorics, dp, math, probabilities

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}$$$.

Input format:
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$$$.

Output format:
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 < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4
1
0
1
2
00
00
4
1000
1110
5
01001
10111

Example output:
1
0
665496254
665496277

Editorial:
Let $$$k$$$ be the number of indices where the characters between two strings are different and $$$f(x)$$$ be the expected number of moves to make two strings equal given that the strings have $$$x$$$ differences. We have to find the value of $$$f(k)$$$.
For all $$$x$$$ where $$$1 \leq x \leq n-1$$$, $$$$$$ \begin{align} f(x) = \frac{x}{n} \cdot [1 + f(x-1)] + \frac{n-x}{n} \cdot [1 + f(x+1)]\\ or,~~~ f(x) = 1 + \frac{x}{n}\cdot f(x-1) + \frac{n-x}{n} \cdot f(x+1) \end{align} $$$$$$
Now, $$$f(0) = 0$$$ and $$$f(1) = 1 + \frac{n-1}{n}f(2)$$$.
We can represent any $$$f(i)$$$ in the form $$$f(i) = a_i + b_i \cdot f(i+1)$$$.
Let, $$$a_{1} = 1$$$ and $$$b_{1} = \frac{n-1}{n}$$$. So, we can write $$$f(1) = a_{1} + b_{1}\cdot f(2)$$$.
When $$$1 \lt i \lt n$$$, $$$f(i) = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot f(i+1)$$$. We can substitute the value of $$$f(i-1)$$$ with $$$a_{i-1} + b_{i-1}\cdot f(i)$$$ and calculate the value of $$$f(i)$$$. Thus we can get the value of $$$a_i$$$ and $$$b_i$$$ using the value of $$$a_{i-1}$$$ and $$$b_{i-1}$$$ by considering $$$a_1$$$ and $$$b_1$$$ as the base case.
We get, $$$a_{i} = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}}$$$ and $$$b_{i} = \frac{n-i}{n-i \cdot b_{i-1}}$$$ for $$$2 \leq i \leq n$$$.
Calculation: Substituting $$$f(i-1) = a_{i-1} + b_{i-1}\cdot f(i)$$$,
$$$$$$ \begin{align} f(i) & = 1 + \frac{i}{n} \cdot [a_{i-1} + b_{i-1}\cdot f(i)] + \frac{n-i}{n} \cdot f(i+1)\\ & = 1 + \frac{i}{n}\cdot a_{i-1} + \frac{i}{n} \cdot b_{i-1} \cdot f(i) + \frac{n-i}{n} \cdot f(i+1)\\ & = \frac{1+\frac{i}{n}\cdot a_{i-1}}{1-\frac{i}{n}\cdot b_{i-1}} + \frac{n-i}{n-i \cdot b_{i-1}}f(i+1)\\ & = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}} + \frac{n-i}{n-i \cdot b_{i-1}}f(i+1)\\ & = a_{i} + b_{i} \cdot f(i+1) \end{align} $$$$$$
So, $$$a_{i} = \frac{n+i\cdot a_{i-1}}{n-i\cdot b_{i-1}}$$$ and $$$b_{i} = \frac{n-i}{n-i \cdot b_{i-1}}$$$ for $$$2 \leq i \leq n$$$.
Similarly, $$$f(n) = 1+f(n-1)$$$.
We can represent any $$$f(i)$$$ in the form $$$f(i) = c_i + d_i \cdot f(i-1)$$$.
Let, $$$c_{n} = 1$$$ and $$$d_{n} = 1$$$. So, we can write $$$f(n) = c_{n} + d_{n}\cdot f(n-1)$$$.
When $$$1 \lt i \lt n$$$, $$$f(i) = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot f(i+1)$$$. We can substitute the value of $$$f(i+1)$$$ with $$$c_{i+1} + d_{i+1}\cdot f(i)$$$ and calculate the value of $$$f(i)$$$. Thus we can get the value of $$$c_i$$$ and $$$d_i$$$ using the value of $$$c_{i+1}$$$ and $$$d_{i+1}$$$ by considering $$$c_n$$$ and $$$d_n$$$ as the base case.
We get, $$$c_{i} = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}}$$$ and $$$d_{i} = \frac{i}{n-(n-i) \cdot d_{i+1}}$$$.
Calculation: Substituting $$$f(i+1) = c_{i+1} + d_{i+1}\cdot f(i)$$$,
$$$$$$ \begin{align} f(i) & = 1 + \frac{i}{n} \cdot f(i-1) + \frac{n-i}{n} \cdot [c_{i+1} + d_{i+1}\cdot f(i)]\\ & = 1 + \frac{i}{n}\cdot f(i-1) + \frac{n-i}{n} \cdot c_{i+1} + \frac{n-i}{n} \cdot d_{i+1} \cdot f(i)\\ & = \frac{1+\frac{n-i}{n}\cdot c_{i+1}}{1-\frac{n-i}{n}\cdot d_{i+1}} + \frac{i}{n-(n-i) \cdot d_{i+1}}f(i-1)\\ & = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}} + \frac{i}{n-(n-i) \cdot d_{i+1}}f(i-1)\\ & = c_{i} + d_{i} \cdot f(i-1) \end{align} $$$$$$
So, $$$c_{i} = \frac{n+(n-i)\cdot c_{i+1}}{n-(n-i)\cdot d_{i+1}}$$$ and $$$d_{i} = \frac{i}{n-(n-i) \cdot d_{i+1}}$$$.
Now, $$$f(i) = c_i + d_i \cdot f(i-1)$$$ and $$$f(i-1) = a_{i-1} + b_{i-1} \cdot f(i)$$$. By solving these two equations, we find that $$$f(i) = \frac{c_i+d_i \cdot a_{i-1}}{1-d_i \cdot b_{i-1}}$$$.
Time Complexity: $$$\mathcal{O}(n\cdot \log m)$$$.