Вы проектируете уровень для компьютерной игры. Этот уровень состоит из $$$n$$$ комнат, расположенных по кругу. Комнаты пронумерованы от $$$1$$$ до $$$n$$$. У каждой комнаты ровно один выход: после завершения $$$j$$$-й комнаты вы отправляетесь в $$$(j+1)$$$-ю комнату (а после завершения $$$n$$$-й комнаты вы отправляетесь в $$$1$$$-ю комнату).
Вам задано описание мультимножества из $$$n$$$ сундуков: ценность сокровища в $$$i$$$-м сундуке равна $$$c_i$$$.
Каждый сундук может быть одного из двух типов:
Игрок начинает в случайной комнате, и у каждой комнаты равная вероятность быть выбранной. Доход игрока равен сумме ценностей сокровищ в тех сундуках, которые он собрал до своего поражения.
Вы можете выбрать порядок, в котором сундуки будут установлены в комнатах. Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ расставьте сундуки таким образом, что:
Обратите внимание, что для каждого $$$k$$$ расстановка выбирается независимо.
Можно показать, что данное математическое ожидание можно представить в виде $$$\frac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ являются неотрицательными целыми числами $$$Q \ne 0$$$. Выведите значения $$$P \cdot Q^{-1} \pmod {998244353}$$$.
В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество комнат и количество сундуков.
Во второй строке записаны $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$) — ценности сокровищ в каждом сундуке.
Выведите $$$n$$$ целых чисел — $$$k$$$-е число должно быть равно минимальному математическому ожиданию дохода игрока, если сундуки расставлены по комнатам в каком-то порядке и ровно $$$k$$$ из сундуков являются мимиками.
Можно показать, что данное математическое ожидание можно представить в виде $$$\frac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ являются неотрицательными целыми числами $$$Q \ne 0$$$. Выведите значения $$$P \cdot Q^{-1} \pmod {998244353}$$$.
2 1 2
499122177 0
8 10 4 3 6 5 10 7 5
499122193 249561095 249561092 873463811 499122178 124780545 623902721 0
В первом примере точные значения минимального математического ожидания равны: $$$\frac 1 2$$$, $$$\frac 0 2$$$.
Во втором примере точные значения минимального математического ожидания равны: $$$\frac{132} 8$$$, $$$\frac{54} 8$$$, $$$\frac{30} 8$$$, $$$\frac{17} 8$$$, $$$\frac{12} 8$$$, $$$\frac 7 8$$$, $$$\frac 3 8$$$, $$$\frac 0 8$$$.
Название |
---|