AT_tupc2023_m.Vivid Colors

觉得 $256^3$ 能表示的颜色数太少了，Aoba 设想了一种扩展 RGB，其中每个参数都是 $0$ 到 $2 \times 10^5$ 之间的实数。

调色板上有 $N$ 种颜料，第 $i$ 种颜色的扩展 RGB 值按 $(R, G, B)$ 顺序为 $(r_i, g_i, b_i)$。

对于扩展 RGB 值为 $(r, g, b)$ 的颜色，定义其鲜艳度为 $(r, g, b)$ 的方差。例如，用 $(0, 120, 480)$ 表示的颜色的鲜艳度为 $\frac{(0 - 200)^2 + (120 - 200)^2 + (480 - 200)^2}{3} = 41600$。

Aoba 想要通过混合调色板上若干种颜色，制作出鲜艳的颜色。

当同时混合多种颜色时，混合后扩展 RGB 每个参数都等于所用颜色该参数的平均值。混合后每个参数的数值可能是非整数。

现从调色板上 $N$ 种颜料中恰好选 $k$ 种进行混合，求混合后颜色的鲜艳度的最大可能值，并对 $998244353$ 取模输出。

有理数 $\bmod{998244353}$ 的定义：可以证明问题要求的值一定是有理数。在本题的约束下，将所求结果表示成最简分数 $\frac{y}{x}$ 时，$x$ 不会被 $998244353$ 整除。此时，存在唯一的整数 $z\ (0 \leq z \leq 998244352)$ 满足 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。请分别对 $k = 1, 2, \ldots, N$ 求出答案。

输入从标准输入读入，格式如下：

$N$ $r_1$ $g_1$ $b_1$ $r_2$ $g_2$ $b_2$ $\vdots$ $r_N$ $g_N$ $b_N$

第 $i$ 行输出 $k = i$ 时的答案。

背景

RGB 值即用 Red（红）、Green（绿）、Blue（蓝）分别以 $0$ 到 $255$ 的值来指定颜色。

如 $(R, G, B) = (0, 0, 128)$ 是海军蓝，$(255, 255, 0)$ 是黄色，若三者都取相同值则为白、灰或黑等单色。

部分分

• 满足额外约束 $N \leq 300$ 的数据集可得 30 分。

样例解释 1

当 $k=2$ 时，混合第 2、3 种颜色得到扩展 RGB 为 $(0, 90, 180)$，鲜艳度为 $\frac{(0-90)^2 + (90-90)^2 + (180-90)^2}{3} = 5400$。

样例解释 2

混合后扩展 RGB 的值可能为非整数。

约束条件

• $2 \leq N \leq 2000$
• $0 \leq r_i, g_i, b_i \leq 2 \times 10^5\ (1 \leq i \leq N)$
• 输入均为整数

由 ChatGPT 5 翻译