页面无法加载？点击这里可能会修复。
Placeholder

#8861
子任务

발굽, 종이, 가위 트리플 1s 1024MB

问题

아마도 "가위바위보"라는 게임에 대해 들어보셨을 것입니다. 소들은 이와 비슷한 "발굽, 종이, 가위"라는 게임을 즐깁니다.

"발굽, 종이, 가위"의 규칙은 간단합니다. 두 마리의 소가 서로 경기를 합니다. 두 소는 모두 셋까지 센 후 동시에 발굽, 종이, 가위 중 하나를 나타내는 손짓을 합니다. 발굽은 가위를 이기고(발굽이 가위를 부술 수 있기 때문), 가위는 종이를 이기며(가위가 종이를 자를 수 있기 때문), 종이는 발굽을 이깁니다(발굽이 종이에 베일 수 있기 때문). 예를 들어, 첫 번째 소가 "발굽" 손짓을 하고 두 번째 소가 "종이" 손짓을 하면 두 번째 소가 이깁니다. 물론 두 소가 같은 손짓을 하면 비길 수도 있습니다.

이제 발굽 종이 가위를 하고 싶어 하는 N (3≤N≤2⋅10^5) 마리의 소가 있으며, 각 소는 고정된 분포에서 선택하는 독립적인 전략을 가지고 있습니다. 구체적으로, i번째 소의 전략은 각각 (\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})의 확률로 발굽, 종이, 가위를 내는 것입니다.

A가 B를 평균적으로 이기고, B가 C를 평균적으로 이기며, C가 A를 평균적으로 이기는 서로 다른 소의 삼조 (A,B,C)는 몇 개입니까? 순환 이동을 통해 같아지는 두 삼조는 동일한 것으로 간주합니다.


输入

첫 번째 줄에는 독립적인 테스트의 개수 T (1≤T≤5⋅10^4)가 주어집니다. 각 테스트는 다음과 같은 형식으로 주어집니다:

첫 번째 줄에는 N이 주어집니다.

다음 N개의 줄에는 각각 세 개의 음이 아닌 정수 h_i, p_i, s_i(0≤h_i,p_i,s_i≤10^9, h_i+p_i+s_i>0)가 주어집니다.

모든 테스트에 대한 N의 합은 다음을 초과하지 않음이 보장됩니다.


输出

트리플의 개수를 출력합니다.

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


子任务

编号 分数 条件
#120分

N \le 10

#230分

N≤7\ 500, 모든 테스트 케이스에 대한 N의 합은 10^4을 초과하지 않습니다.

#350分

추가 제약 조건 없음


示例 

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)가 있습니다.


来源

USACO 2026 First Contest, Platinum
需要登录才能编写代码。