| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 17 | 13 | 13 | 86.667% |
세 정수 $A_1$, $A_2$, $A_3$이 주어질 때, 다음 조건을 만족하는 루트 있는 이진 트리의 개수를 구하라.
이때 루트 있는 이진 트리는 좌/우 자식을 구분하며, 정점에는 번호가 부여되지 않는다.
두 루트 있는 이진 트리가 서로 다르게 세어질 조건은 다음과 같은 정점이 하나 이상 있는 경우이다.
예시로, 다음 두 트리를 보자.
두 트리 모두 $(A_1,A_2,A_3) =(3,4,1)$인 트리이다. 두 트리의 루트는 $R$로 표기되어 있다. 왼쪽 트리는 왼쪽 $\rightarrow$ 오른쪽 $\rightarrow$ 왼쪽 경로를 따라갔을 때 정점 $x$가 있지만, 오른쪽 트리는 해당 경로를 따라갔을 때 도달하는 정점이 없기 때문에 서로 다른 트리로 세어진다.
첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\leq T\leq 100\, 000)$
다음 $T$개의 줄에 걸쳐 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되며, 세 정수 $A_1,A_2,A_3$가 공백으로 구분되어 주어진다. $(0\leq A_1,A_2,A_3\leq 1\, 000\, 000;A_1+A_2+A_3>0)$
각 테스트 케이스마다 한 줄에 문제에서 요구하는 트리의 개수를 $998\, 244\, 353$으로 나눈 나머지를 출력한다.
5 2 0 0 2 1 0 3 1 1 4 3 3 6 0 4
2 5 14 0 28
2 3 4 1 3 5 1
800 2464