[AdditionalFile5595.zip](file://AdditionalFile5595.zip?type=additional_file)

#5595. 「USACO 2026 First Platinum」Hoof, Paper, Scissors Triples

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 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