시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 156 | 51 | 40 | 34.483% |
파스칼 행렬은 크기가 무한대이며 다음과 같이 정의한다. (행과 열 번호는 0부터 시작한다)
Pascal[row, column] = Comb(row, column) for 0 ≤ column ≤ row
위의 경우를 제외한 곳은 모두 0이다. Comb(n, k)는 조합이다.
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ... |
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ... |
1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ... |
1 | 3 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | ... |
1 | 4 | 6 | 4 | 1 | 0 | 0 | 0 | 0 | 0 | ... |
1 | 5 | 10 | 10 | 5 | 1 | 0 | 0 | 0 | 0 | ... |
1 | 6 | 15 | 20 | 15 | 6 | 1 | 0 | 0 | 0 | ... |
1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | 0 | 0 | ... |
1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 | 0 | ... |
1 | 9 | 36 | 84 | 126 | 126 | 84 | 36 | 9 | 1 | ... |
. | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . |
파스칼 행렬의 제곱을 구하는 프로그램을 작성하시오.
PascalP = Pascal × Pascal × ... × Pascal
첫째 줄에 테스트 케이스의 개수 K (1 ≤ K ≤ 1000)가 주어진다.
각 테스트 케이스는 네 정수로 이루어져 있다. 첫 번째 정수는 테스트 케이스 번호이다. 두 번째 정수는 P이다. (1 ≤ P ≤ 100,000) 세 번째 정수와 네 번째 정수는 R과 C이다. (0 ≤ C ≤ R ≤ 100,000)
각 테스트 케이스마다 테스트 케이스 번호를 출력하고, PascalP의 R행 C열의 값을 출력한다. 답이 64비트 정수 범위를 넘어가지 않는 입력만 주어진다.
3 1 1 8 3 2 9 21 13 3 200 100000 99998
1 56 2 8759577256290 3 199998000000000