题目描述

题目译自 USACO 2026 First Contest, Platinum Problem 1. Hoof, Paper, Scissors Triples

你可能听说过“剪刀、石头、布”的游戏。奶牛们喜欢玩一个类似的游戏，叫做“蹄子、布、剪刀”。

“蹄子、布、剪刀”的规则很简单。两头奶牛进行对抗。她们都数到三，然后同时做出一个代表蹄子、布或剪刀的手势。蹄子胜过剪刀（因为蹄子能砸烂剪刀），剪刀胜过布（因为剪刀能剪破布），布胜过蹄子（因为蹄子会被纸划伤）。例如，如果第一头奶牛出“蹄子”的手势，而第二头出“布”的手势，那么第二头奶牛获胜。当然，如果两头奶牛做出相同的手势，也可能打平。

现在有 $N$（$3\le N\le 2\cdot 10^5$）头奶牛想要玩蹄子、布、剪刀，她们每头都独立地根据某个固定的分布采用策略。具体来说，第 $i$ 头奶牛出蹄子、布或剪刀的概率分别为 $\left(\frac{h_i}{h_i+p_i+s_i}, \frac{p_i}{h_i+p_i+s_i}, \frac{s_i}{h_i+p_i+s_i} \right)$。

有多少个不同的奶牛三元组 $(A, B, C)$ 满足：平均情况下 $A$ 胜过 $B$，平均情况下 $B$ 胜过 $C$，且平均情况下 $C$ 胜过 $A$？如果一个三元组可以通过循环移位变为另一个，我们认为它们是相同的。

输入格式

第一行包含 $T$（$1\le T\le 5\cdot 10^4$），即独立测试数据的组数。每组测试数据的格式如下：

第一行包含 $N$。

接下来的 $N$ 行，每行包含三个非负整数 $h_i, p_i, s_i$（$0\le h_i,p_i,s_i\le 10^9, h_i+p_i+s_i>0$）。

保证所有测试数据中 $N$ 的总和不超过 $3 \cdot 10^5$。

输出格式

输出三元组的数量。

注意：本题涉及的整数较大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 long long）。

2
4
1 0 0
1 0 0
0 1 0
0 0 1
10
20410069 21445597 257862632
114108992 287498302 113278897
607994331 143503714 631122722
337497016 270153603 320256324
633717786 631078144 493265815
202783212 612643590 560838949
713379081 42803063 58996167
293262767 470686180 220651551
656404313 408797935 345461691
959196297 827681918 591519393

2
32

对于第一个测试用例，有两个三元组：$(1,3,4)$ 和 $(2,3,4)$。

数据范围与提示

• 测试点 2-3：$N\le 10$
• 测试点 4-9：$N \le 7500$，所有测试用例中 $N$ 的总和不超过 $10^4$
• 测试点 10-21：无额外约束

供题：Richard Qi