Вам даны две бинарные строки $$$a$$$ и $$$b$$$ длины $$$n$$$. На каждом шаге строка $$$a$$$ изменяется следующим образом.
Чему равняется математическое ожидание количества шагов, необходимого для того, чтобы обе строки стали равными в первый раз?
Бинарная строка — это строка, в которой каждый символ равен либо $$$\tt{0}$$$, либо $$$\tt{1}$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — длина строк.
Вторая строка каждого набора содержит бинарную строку $$$a$$$ длиной $$$n$$$.
Третья строка каждого набора содержит бинарную строку $$$b$$$ длины $$$n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.
Для каждого набора входных данных выведите математическое ожидание количества ходов по модулю $$$998\,244\,353$$$.
Формально, пусть $$$M = 998\,244\,353$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.
41012000041000111050100110111
1 0 665496254 665496277
В первом наборе индекс $$$1$$$ выбирается случайным образом и $$$a_1$$$ изменяется на противоположное значение. После этого строки $$$a$$$ и $$$b$$$ равны. Ожидаемое количество ходов — $$$1$$$.
Во втором наборе строки $$$a$$$ и $$$b$$$ уже равны. Таким образом, ожидаемое количество ходов равно $$$0$$$.
Ожидаемое количество ходов для третьего и четвертого наборов составляет $$$\frac{56}{3}$$$ и $$$\frac{125}{3}$$$ соответственно.
| Codeforces Round 848 (Div. 2) |
|---|
| Закончено |
