라스칼 삼각형
시간 제한1초메모리 제한128 MB
나눗셈이 포함된 재귀 규칙으로 정의되는 '래스칼 삼각형'에서 최대 5만 크기의 n, m에 대해 R(n,m) 값을 1000개 질의까지 효율적으로 계산합니다.
문제
라스칼 삼각형은 파스칼 삼각형과 비슷한 규칙으로 만들어진다.
맨 위 줄을 0번째 줄이라고 한다. i번째 줄에는 i+1개의 수가 있으며, 왼쪽부터 0번째부터 i번째까지 번호가 붙는다. R(i, j)는 i번째 줄의 j번째 수를 뜻한다.
범위를 벗어난 위치는 0으로 둔다.
R(n, m) = 0 (n < 0 또는 m < 0 또는 m > n)
각 줄의 첫 번째 수와 마지막 수는 1이다.
R(n, 0) = R(n, n) = 1
나머지 수는 서쪽 값과 동쪽 값을 곱한 뒤 1을 더하고, 북쪽 값으로 나누어 구한다.
이를 식으로 쓰면 다음과 같다.
R(n+1, m+1) = (R(n, m) * R(n, m+1) + 1) / R(n-1, m)
주어진 n과 m에 대해 R(n, m)을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 <= T <= 1,000)
각 테스트 케이스는 한 줄에 두 정수 n과 m으로 주어진다. (0 <= m <= n <= 50,000)
출력
각 테스트 케이스마다 R(n, m)을 한 줄에 하나씩 출력한다.