CF1380G Circular Dungeon

你正在为一个电子游戏设计关卡。该关卡由 $n$ 个房间组成，这些房间按环形排列。房间编号为 $1$ 到 $n$。每个房间恰好有一个出口：完成第 $j$ 个房间后可以进入第 $(j+1)$ 个房间（完成第 $n$ 个房间后可以进入第 $1$ 个房间）。 你得到了 $n$ 个宝箱的描述：第 $i$ 个宝箱的宝藏价值为 $c_i$。 每个宝箱可以是以下两种类型之一： - 普通宝箱 —— 玩家进入有此宝箱的房间时，会拿走宝藏并前往下一个房间； - 拟态宝箱 —— 玩家进入有此宝箱的房间时，会被宝箱吞噬并失败。 玩家会随机从任意一个房间开始，每个房间被选中的概率相同。玩家的收益等于在失败前收集到的所有宝藏价值之和。 你可以选择将宝箱按任意顺序放入房间。对于每个 $k$（$1$ 到 $n$），请将宝箱放入房间，使得： - 每个房间恰好有一个宝箱； - 恰好有 $k$ 个宝箱是拟态宝箱； - 玩家收益的期望值尽可能小。 请注意，对于每个 $k$，宝箱的放置可以独立选择。 可以证明，答案形式为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是非负整数且 $Q \ne 0$。请输出 $P \cdot Q^{-1} \bmod {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 \cdot Q^{-1} \bmod {998244353}$。

在第一个样例中，最小期望值的精确值为：$\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}$。 由 ChatGPT 4.1 翻译