Informatica Online Judge

  Combination Memoization [1292 / 050C]

Time Limit(Test case) : 750(ms)
Number of users who solved : 8   Total Tried : 101


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 이상헌)]

Background

경곽이는 수업시간에 배운 이항계수(binomial coefficient)의 점화식에 대해 공부하고자 한다. 흔히 nCr로 불리는 이항계수는, 정보과학에서 다음과 같은 재귀함수로 구할 수 있다(다음 예시는 int 범위 내에서만 작동한다).


int C(int n, int r)
{
assert(0<=r&&r<=n);
if(dp[n][r]) return dp[n][r];
if(n==0) return dp[n][r]=1;
if(r==0) return dp[n][r]=C(n-1,r);
if(n==r) return dp[n][r]=C(n-1,r-1);
return dp[n][r]=C(n-1,r)+C(n-1,r-1);
}


여기서 dp[n][r]은 한 번 계산한 nCr의 값을 저장해 놓는 공간이다. nCr은 언제나 일정하므로, 한 번만 계산해서 저장해놓으면 계속 쓸 수 있다.

이를 메모이제이션(memoization)이라고 한다.

이러한 방식으로 nCr을 구하고자 할 때는, 초기에 상당히 많은 값을 조사해야 한다.

예를 들어, dp[2][1]을 C(2,1)로 구하고자 하면 C(2,1)은 C(1,0) 및 C(1,1)을 호출하고, C(1,0)은 C(0,0)을 호출하며, C(0,0)은 1을 return하는 동시에 dp[0][0]에 1을 저장한다.

이후, C(1,1) 역시 호출되나 dp[0][0]이 이미 저장되어 있기에 추가적인 계산 없이 바로 계산해놓은 값을 return할 수 있다.

결과적으로 C(2,1)을 호출하면 4개의 값을 새로 알게 되는 셈이다((2,1),(1,0),(0,0),(1,1)).

반면, 이렇게 계산되어 있는 상태에서 C(3,1)을 구하고자 하면 C(2,0), C(2,1)이 호출되나 우리는 이미 C(2,1)을 알고 있으므로 C(2,0)만 추가적으로 조사하면 되며, 이는 다시 우리가 알고 있는 C(1,0)을 호출하므로 2개의 값만 새로 갱신하게 된다.((3,1),(2,0)).

경곽이는 이렇게 memoization을 통해서 nCr을 구하고자 할 때, 매번 몇 개의 값을 새로 조사해야하는지 알고 싶다.

경곽이를 도와 매번 nCr을 위의 함수와 같은 방식으로 구할 때 몇 개의 칸이 갱신되는지 구해보자.

Input

첫번째 줄에 구하고자 하는 이항계수들의 개수 q가 입력된다.
그 다음 q개의 줄에는 C(n,r)에 입력될 두 개의 정수 n, r이 입력된다.

[입력값의 정의역]
1 <= q <= 80000
0 <= r <= n <= 80000

[SubTask Info]
#1 (10%): 1 <= q <= 10, 0 <= r <= n <= 20을 만족한다.
#2 (20%): 1 <= q <= 1000, 0 <= r <= n <= 1000을 만족한다.
#3 (20%): 1 <= q <= 5000, 0 <= r <= n <= 10000을 만족한다.
#4 (50%): 1 <= q <= 80000, 0 <= r <= n <= 80000을 만족한다.

Output

q개의 줄에 각각 C(n,r)을 호출할 때 갱신되는 dp 배열의 칸 개수를 출력한다.

IO Example

입력 1
4
2 1
3 1
6 3
3 2

출력 1
4
2
10
0

입력 2
3
4 2
5 4
6 3


출력 2
9
4
5



1번째 입력의 경우,

C(2,1)은 4개의 값을 갱신한다: (2,1), (1,0), (0,0), (1,1).

C(3,1)은 2개의 값을 갱신한다: (3,1), (2,0).

C(6,3)은 10개의 값을 갱신한다: (6,3), (5,2), (4,1), (3,0), (4,2), (3,2), (2,2), (5,3), (4,3), (3,3).

C(3,2)은 이미 3번째 경우에서 조사되었다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]