#P18202. Vivid Colors
Vivid Colors
Vivid Colors
通常,RGB 模型分别给红、绿、蓝三个分量赋予 到 的数值,用来表示颜色。例如, 表示藏青色, 表示黄色。当三个分量相同时,得到白色、灰色或黑色等灰度颜色。
Aoba 觉得 种颜色还不够,于是设计了扩展 RGB 模型,允许每个分量取 到 之间的实数。
调色板上有 份颜料,第 份颜料的扩展 RGB 值为 。
对于扩展 RGB 值为 的颜色,定义其鲜艳度为三个分量的方差。令 ,则鲜艳度为
例如, 的三个分量平均值为 ,鲜艳度为
$$\frac{(0-200)^2+(120-200)^2+(480-200)^2}{3}=41600.$$将多份颜料同时混合,得到的颜色的扩展 RGB 值,是这些颜料原有 RGB 值的逐分量平均。具体地,混合 份 RGB 值分别为 的颜料,得到
$$\left(\frac{r_1+\cdots+r_k}{k},\frac{g_1+\cdots+g_k}{k},\frac{b_1+\cdots+b_k}{k}\right).$$混合后的分量不一定是整数。每份给定颜料至多使用一次。
对于每个 ,求从这 份颜料中选择恰好 份同时混合,能够得到的最大鲜艳度,并按下述方法输出模 的值。
有理数取模的定义
可以证明答案是有理数。将它写成最简分数 后,题目保证 不被 整除。存在唯一的整数 使
输出这个 。这里先在实际有理数意义下求最大值,再对得到的答案取模。
输入格式
N
r_1 g_1 b_1
...
r_N g_N b_N
所有输入均为整数,满足:
- ;
- 。
输入只有一组数据。
输出格式
输出 行。第 行输出混合恰好 份颜料所能得到的最大鲜艳度,按上述定义模 。
样例 1
输入
3
180 0 0
0 180 180
0 0 180
输出
7200
5400
800
说明
当 时,混合第二份和第三份颜料,得到 ,鲜艳度为
样例 2
输入
6
30594 32322 46262
63608 59020 98436
90150 32740 67209
82886 4627 54813
3112 67989 74995
60872 9967 9051
输出
715162883
838096208
930330061
405079896
880764907
526006962