2099: [USACO 2026 First Contest, Platinum] Problem 1. Hoof, Paper, Scissors Triples

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 ≤ N ≤ 2 ⋅ 10⁵) cows who want to play hoof paper scissors, and they each independently have a strategy of drawing from some fixed distribution. In particular, the ith cow's strategy is to play hoof, paper, or scissors with probabilities  , 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.

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++).

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