발굽, 보, 가위 삼중쌍

"가위, 바위, 보" 게임을 들어 본 적이 있을 것이다. 소들은 이와 비슷한 "발굽, 보, 가위"라는 게임을 즐겨 한다.

"발굽, 보, 가위"의 규칙은 간단하다. 두 소가 서로 대결한다. 둘 다 셋을 센 다음, 동시에 발굽, 보, 가위 중 하나를 나타내는 손짓을 한다. 발굽은 가위를 이기고 (발굽이 가위를 부술 수 있으므로), 가위는 보를 이기고 (가위가 종이를 자를 수 있으므로), 보는 발굽을 이긴다 (발굽이 종이에 베일 수 있으므로). 예를 들어, 첫 번째 소가 "발굽"을 내고 두 번째 소가 "보"를 내면 두 번째 소가 이긴다. 물론 두 소가 같은 손짓을 하면 비길 수도 있다.

이제 발굽 보 가위를 하고 싶어 하는 \(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를 이기고, B가 평균적으로 C를 이기고, C가 평균적으로 A를 이기는 서로 다른 소의 삼중쌍 (A,B,C)는 몇 개인가? 한 삼중쌍이 다른 삼중쌍의 순환 이동과 같으면 두 삼중쌍을 같은 것으로 간주한다.

Problem credits: Richard Qi

SCORING

• 입력 2-3: \(N\le 10\)
• 입력 4-9: \(N \le 7500\), 모든 테스트에 걸친 \(N\)의 합이 \(10^4\)를 넘지 않는다
• 입력 10-21: 추가 제약 없음.

Problem credits: Richard Qi

첫째 줄에 독립적인 테스트의 수 \(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\)의 합이 일정 한도를 넘지 않음이 보장된다.

삼중쌍의 개수를 출력한다.

참고: 이 문제에 등장하는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")을 사용해야 할 수 있다.

riseoj 작성

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