Flexible String Revisit

题意翻译

给出两个长度均为 $n(n\leq 10^6)$ 的 01 串 $S$ 和 $T$ 每次随机将 $S$ 中的某一位取反 问：第一次 $S = T$ 时操作次数的期望

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

4
1
0
1
2
00
00
4
1000
1110
5
01001
10111

输出样例 #1

1
0
665496254
665496277

说明

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.

**题目大意：**

题目描述了两个长度相同的01字符串\( S \)和\( T \)，每次可以随机选择\( S \)中的一个位置并将其字符从0变为1，或从1变为0。问使得\( S = T \)的期望操作次数是多少。

**输入输出数据格式：**

- **输入格式：**
- 第一行包含一个整数\( t \)（\( 1 \leq t \leq 10^5 \)），表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含一个整数\( n \)（\( 1 \leq n \leq 10^6 \)），表示字符串的长度。
- 第二行包含一个长度为\( n \)的01字符串\( a \)。
- 第三行包含一个长度为\( n \)的01字符串\( b \)。
- 保证所有测试用例的\( n \)之和不超过\( 10^6 \)。

- **输出格式：**
- 对于每个测试用例，输出一个整数，表示使得\( S = T \)的期望操作次数模\( 998\,244\,353 \)的结果。
- 正式地说，答案可以表示为不可约分数\( \frac{p}{q} \)，其中\( p \)和\( q \)是整数，且\( q \not \equiv 0 \pmod{M} \)。输出\( p \cdot q^{-1} \bmod M \)的整数结果，即输出满足\( 0 \le x < M \)和\( x \cdot q \equiv p \pmod{M} \)的整数\( x \)。**题目大意：** 题目描述了两个长度相同的01字符串\( S \)和\( T \)，每次可以随机选择\( S \)中的一个位置并将其字符从0变为1，或从1变为0。问使得\( S = T \)的期望操作次数是多少。 **输入输出数据格式：** - **输入格式：** - 第一行包含一个整数\( t \)（\( 1 \leq t \leq 10^5 \)），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含一个整数\( n \)（\( 1 \leq n \leq 10^6 \)），表示字符串的长度。 - 第二行包含一个长度为\( n \)的01字符串\( a \)。 - 第三行包含一个长度为\( n \)的01字符串\( b \)。 - 保证所有测试用例的\( n \)之和不超过\( 10^6 \)。 - **输出格式：** - 对于每个测试用例，输出一个整数，表示使得\( S = T \)的期望操作次数模\( 998\,244\,353 \)的结果。 - 正式地说，答案可以表示为不可约分数\( \frac{p}{q} \)，其中\( p \)和\( q \)是整数，且\( q \not \equiv 0 \pmod{M} \)。输出\( p \cdot q^{-1} \bmod M \)的整数结果，即输出满足\( 0 \le x < M \)和\( x \cdot q \equiv p \pmod{M} \)的整数\( x \)。