У Кэрол есть последовательность $$$s$$$ из $$$n$$$ неотрицательных целых чисел. Она хочет сыграть с Алисой и Бобом в «Угадайку».
Игра устроена следующим образом. Сначала Кэрол случайно выберет два целых индекса $$$i_a$$$ и $$$i_b$$$ из диапазона $$$[1, n]$$$ и обозначит $$$a=s_{i_a}$$$, $$$b=s_{i_b}$$$. Обратите внимание: $$$i_a$$$ и $$$i_b$$$ могут совпасть.
Затем Кэрол сообщит:
Обратите внимание: Кэрол не сообщит никакой информации об $$$s$$$ ни Алисе, ни Бобу.
Затем начинается процесс угадывания. Алиса и Боб ходят по очереди, причём первой ходит Алиса. Цель обоих игроков — выяснить, какое из утверждений верно: $$$a < b$$$, $$$a > b$$$, или $$$a = b$$$.
На своём ходу игрок может сделать одно из двух:
Алиса и Боб слышат фразы друг друга и могут использовать их в своих рассуждениях. Оба игрока достаточно умны. Сказать «Я знаю» они могут только в том случае, если точно уверены в ответе.
Найдите математическое ожидание числа шагов в такой игре. Выведите ответ по модулю $$$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}$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$s_1,s_2,\ldots, s_n$$$ ($$$0 \le s_i < 2^{30}$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно число — ответ на задачу по модулю $$$998\,244\,353$$$.
422 330 0 039 9 6834124838 0 113193378 8 321939321 113193378 9463828 99
499122179 1 332748120 77987843
В первом наборе входных данных есть всего $$$4$$$ возможные ситуации:
Математическое ожидание числа шагов равно $$$\frac{2+3+2+3}{4}=\frac{5}{2}=499122179\pmod{998244353}$$$.
Рассмотрим первый случай, когда $$$a=2$$$, $$$b=2$$$. Процесс угадывания происходит следующим образом.
На первом ходу Алиса думает так: «Я знаю, что $$$a=2, a\mid b=2$$$. Можно сделать вывод, что $$$b=0$$$ или $$$b=2$$$, но какой из этих двух случаев имеет место — пока неясно». Поэтому она говорит: «Я не знаю».
На втором ходу Боб думает так: «Я знаю, что $$$b=2, a\mid b=2$$$. Можно сделать вывод, что $$$a=0$$$ или $$$a=2$$$. Однако если $$$a=0$$$, то Алиса на своём ходу уже бы сказала, что $$$a<b$$$. Но она этого не сказала. Значит, $$$a=2$$$». Поэтому он говорит: «Я знаю, $$$a=b$$$». Игра завершается.
Во втором наборе входных данных, при $$$a=0$$$, $$$b=0$$$, Алиса сразу заключает, что $$$a=b$$$. Ожидаемое число ходов равно $$$1$$$.
Название |
---|