← 返回题目列表

AtCoder · tupc2023_m

M. 鲜艳的色彩

中文机器翻译题面 查看原题

配点 : 100 点

背景

RGB 值是通过用以下数值指定 Red(红色)、Green(绿色)、Blue(蓝色)各色来指定颜色的数值。 0 以上 255 以下的值指定颜色。

(R, G, B) = (0, 0, 128) 表示海军蓝,(255, 255, 0) 表示黄色。 另一方面,如果 (R, G, B) 全部相同,则表示白色、灰色、黑色等单色。

問題文

表示可能的颜色数量 256^3 认为较少,青叶小姐发明了每个参数取以下实数值的扩展 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) 由分散来定义。 例如 (r, g, b) = (0, 120, 480) 表示的颜色的鲜艳度是 \frac{(0 - 200)^2 + (120 - 200)^2 + (480 - 200)^2}{3} = 41600 。

青叶小姐想通过混合调色板上的几种颜色来制作鲜艳的颜色。

当同时混合多种颜色时,会生成各扩展 RGB 值参数为原色平均值的颜色。 请注意,混色后的参数值可能不是整数。

调色板上的 N 种颜料中只是 执行 k 个,当选择并同时混合它们时, 混合后的颜色鲜艳度可能达到的最大值是 \bmod{998244353} 找到它。

有理数 \bmod{998244353} 的定义 可以证明,这个问题所求的值是有理数。 另外,在这个问题的约束下,所求的期望值以最简分数表示时, \frac{y}{x} 被 x 是 在 998244353 整除是不可能的。 这时, xz \equiv y \pmod{998244353} 输出有多少个 0 以上 998244352 的整数 给出了 z 是唯一确定的。这个 请回答 z 。

以上问题 请解决 k = 1, 2, \ldots, N 。

制約

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

部分点

  • 附加限制 如果正确答案是满足 N \leq 300 的数据集 给出 30 点。 如果您正确回答了所有满足

入力

输入是按以下格式从标准输入给出的。

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

出力

i 在线 k = i 的答案。 对于第


入力例 1

3
180 0 0
0 180 180
0 0 180

出力例 1

7200
5400
800

k = 2 时,2, 3 第几种颜色被混合时,其扩展 RGB 值会生成 (0, 90, 180) 的颜色。 这种颜色的鲜艳度为 \frac{(0-90)^2 + (90-90)^2 + (180-90)^2}{3} = 5400 。


入力例 2

6
30594 32322 46262
63608 59020 98436
90150 32740 67209
82886 4627 54813
3112 67989 74995
60872 9967 9051

出力例 2

715162883
838096208
930330061
405079896
880764907
526006962

混合后的颜色的扩展 RGB 值可能会是非整数。