Flexible String Revisit (Codeforces 1778D)
Tags: 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: 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: 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}$$$.

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.

Sample Inputs:
4
1
0
1
2
00
00
4
1000
1110
5
01001
10111

Sample Outputs:
1
0
665496254
665496277

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
MOD = int(1000000000.0 + 7)
MD9 = int(998244353)
INF = int(1e+20)
n = 1000010
inv = [0] * (n + 1)
inv[1] = 1
for i in range(2, n + 1):
    inv[i] = (MD9 - MD9 // i) * inv[MD9 % i] % MD9

def solve():
    n = II()
    a = I()
    b = I()
    same = 0
    for (x, y) in zip(a, b):
        if x == y:
            same += 1
    if same == n:
        print(0)
        return
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(1, n):
        dp[i + 1] = 1 + i * (dp[i] + 1) * inv[n - i]
        dp[i + 1] %= MD9
    res = 0
    for i in range(same + 1, n + 1):
        res += dp[i]
        res %= MD9
    print(res)
    return
N = II()
for _ in range(N):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
mod = 998244353
inv = [0]
for i in range(1, 10 ** 6 + 1):
    inv.append(pow(i, mod - 2, mod))
for _ in range(t):
    n = int(input())
    a = input().rstrip()
    b = input().rstrip()
    if n == 1:
        if a == b:
            print(0)
        else:
            print(1)
        continue
    cnt = 0
    for i in range(n):
        if a[i] != b[i]:
            cnt += 1
    if cnt == 0:
        print(0)
        continue
    ans = 1
    A = [1]
    for i in range(1, n):
        tmp = (i * ans + n) % mod * inv[n - i]
        ans = tmp % mod
        A.append(ans)
    ans = 0
    for i in range(cnt):
        ans += A[-1 - i]
        ans %= mod
    print(ans)

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = 998244353

def fastfrac(a, b, M):
    numb = pow(b, M - 2, M)
    return a % M * (numb % M) % M

def main(t):
    n = int(input())
    s1 = input()
    s2 = input()
    (same, diff) = (0, 0)
    for i in range(n):
        if s1[i] != s2[i]:
            diff += 1
        else:
            same += 1
    dp = [0] * (n + 1)
    temp = [0] * n
    temp[0] = 1
    for i in range(1, n):
        temp[i] = temp[i - 1] * i
        temp[i] += n
        temp[i] = fastfrac(temp[i], n - i, M)
    for i in range(n - 1, -1, -1):
        dp[i] = (dp[i + 1] + temp[i]) % M
    ans = dp[same]
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1