P14983 [USACO26JAN1] Hoof, Paper, Scissors Triples P

你可能听说过游戏“石头、布、剪刀”。奶牛们喜欢玩一个类似的游戏，他们称之为“蹄子、布、剪刀”。 “蹄子、布、剪刀”的规则很简单。两头奶牛相互对战。它们都数到三，然后同时做出一个手势，代表蹄子、布或剪刀。蹄子赢剪刀（因为蹄子可以砸碎剪刀），剪刀赢布（因为剪刀可以剪布），布赢蹄子（因为蹄子可能被布划伤）。例如，如果第一头奶牛做出“蹄子”手势，第二头奶牛做出“布”手势，那么第二头奶牛获胜。当然，如果两头奶牛做出相同的手势，也可能平局。 现在有 $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"）。**

对于第一个测试用例，有两个三元组：$(1, 3, 4)$ 和 $(2, 3, 4)$。 --- - 输入 $2$-$3$：$N\le 10$ - 输入 $4$-$9$：$N \le 7500$，所有测试的 $N$ 之和不超过 $10^4$ - 输入 $10$-$21$：无额外约束。 翻译由 DeepSeek V3 完成