You have probably heard of the game "Rock, Paper, Scissors". The cows like to
play a similar game they call "Hoof, Paper, Scissors".

The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each
other. They both count to three and then each simultaneously makes a gesture
that represents either a hoof, a piece of paper, or a pair of scissors. Hoof
beats scissors (since a hoof can smash a pair of scissors), scissors beats paper
(since scissors can cut paper), and paper beats hoof (since the hoof can get a
papercut). For example, if the first cow makes a "hoof" gesture and the second a
"paper" gesture, then the second cow wins. Of course, it is also possible to
tie, if both cows make the same gesture.

Now there are \(N\) (\(3\le N\le 2\cdot 10^5\)) cows who want to play hoof paper
scissors, and they each independently have a strategy of drawing from some fixed
distribution. In particular, the \(i\)th cow's strategy is to play hoof, paper, or
scissors with probabilities
\(\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)\),
respectively.

How many distinct triples of cows (A,B,C) are there such that A beats B on
average, B beats C on average, and C beats A on average? We consider two triples
the same if one equals the other up to a cyclic shift.

Problem credits: Richard Qi

SCORING

• Inputs 2-3: \(N\le 10\)
• Inputs 4-9: \(N \le 7500\), the sum of \(N\) over all tests does not exceed \(10^4\)
• Inputs 10-21: No additional constraints.

Problem credits: Richard Qi

The first line contains \(T\) (\(1\le T\le 5\cdot 10^4\)), the number of independent
tests. Each test is specified in the following format:

The first line contains \(N\).

The next \(N\) lines each contain three non-negative integers \(h_i\), \(p_i\), \(s_i\)
(\(0\le h_i,p_i,s_i\le 10^9, h_i+p_i+s_i>0\)).

It is guaranteed that the sum of \(N\) over all tests does not exceed

Output the number of triples.

Note: The large size of integers involved in this problem may require the use
of 64-bit integer data types (e.g., a "long long" in C/C++).

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > First Contest > Platinum