11/18 이항계수의 합

삼성 코드그라운드에서 제공하는 알고리즘에 관한 개인적인 풀이를 정리했습니다.

아래 사이트에서 직접 풀어보실 수 있습니다.

 

https://www.codeground.org/practice

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

 

 

 

 

이 문제는 먼저 식을 간단하게 하는 과정이 필요하다. 주어진 식은 다음과 같다.

$$\sum_{i=0}^{N}\sum_{j=0}^{M}\binom{i+j}{i}=\sum_{i=0}^{N}\left (\binom{i}{i} + \binom{i+1}{i}+\binom{i+2}{i} + \cdot \cdot \cdot + \binom{i+M}{i}\right)$$

 

 

 

 

이 식은 이항 계수 법칙 $$\binom{i}{i} + \binom{i+1}{i}+\binom{i+2}{i} + \cdot \cdot \cdot + \binom{i+M}{i} = \binom{i+M+1}{i+1}$$ 에 의해 다음 식과 같아진다.

$$\sum_{i=0}^{N}\binom{i+M+1}{i+1}=\sum_{i=0}^{N}\binom{i+M+1}{i+1}=\binom{M+1}{1}+\binom{M+2}{2}+\cdot\cdot\cdot+\binom{M+N+1}{N+1} $$

 

 

 

 

이 식은 다시 이항 계수 법칙

$$\binom{M+1}{1}+\binom{M+2}{2}+\cdot\cdot\cdot+\binom{M+N+1}{N+1}=\binom{M+N+2}{N+1}$$

에 의해 최종적으로 이렇게 간소화 될 수 있다.

 

 

 

 

$$\sum_{i=0}^{N}\sum_{j=0}^{M}\binom{i+j}{i}=\binom{M+N+2}{N+1}$$

 

 

 

 

이렇게 주어진 식을 간소화하면 문제는 $$_{N+M+2}\textrm{C}_{N+1}\; mod\; 1000000007  = \frac{(N+M+2)!}{(N+1)!(M+1)!}\; mod\; 1000000007$$

로 바뀐다.

N과 M이 0 이상 1000000 이하이므로 답을 구하기 위해 팩토리얼 연산을 할 때 오버플로우에 빠질 수 있는데, 이를 방지하기 위해 곱셈을 할 때마다 10억7과 나머지 연산을 해줘야 한다. 또한 테스트 케이스가 최대 10000개이므로 테스트 케이스가 들어올 떄마다 팩토리얼 값을 구하면 시간초과가 발생하므로 미리 전처리 과정을 통해서 팩토리얼 값을 구해야 한다.

 

 

 

 

 

계산 과정에 나눗셈이 들어가기 때문에 모듈러 연산의 분배법칙을 사용할 수 없는데, 이는 (N+1)!(M+1)!로 나누는 대신 (N+1)!(M+1)!의 modular 1000000007 상에서의 역원을 곱하는 것으로 해결할 수 있다. 역원을 구하는 과정은 다음 사이트를 참고했다.

 

 

 

https://koosaga.com/63

이항계수 (nCr) mod p 계산하기

 

 

 

 

이 사이트에는 nCr(mod p)를 구하기 위한 다양한 방법들이 나와있었다. 그 중에서 나는 시간복잡도가 O(n+logp)인 3번째 방법을 사용했다. 이 방법을 간단하게 소개하면 이렇다.

 

 

 

 

DIV=1000000007

N, M의 최댓값이 1000000이므로 N+M+2의 최댓값은 2000002 이다.

 

 

 

 

1. 1! mod DIV ~2000002! mod DIV 값을 O(n)시간만에 구한다.

2. (2000002)!^-1 = (2000002)!^(p-2) 값을 분할 정복을 통해 O(logp) 시간만에 구한다.

3. (n-1)!^-1 = n * (n!)^-1 인 것을 이용하여 (2000001)!^-1, (2000000)!^-1, ... ,1!^-1의 값을

O(n) 시간만에 구한다.

4. 시간 복잡도는 O(n+logp)

 

 

 

 

이러한 과정을 거쳐 미리 1!~2000002! 값과 mod 100000007 상에서의 역원을 구해두고, 이를 각각의 테스트 케이스마다 활용하면 답을 구할 수 있다.

 

 

 

 

 

전체 코드는 다음과 같다.

#include <iostream>

using namespace std;

int Answer; //이항계수의 합
const int DIV = 1000000007;
const int MAX = 2000002;
int fac[2000003];
long long facInv[2000003];

long long getInvN(long long x, int n) {
	if (n == 0) return 1;
	if (n == 1) return x;
	if (n % 2 == 0) return getInvN((x * x)%DIV, n / 2)%DIV;
	else return (x * getInvN((x * x)%DIV, (n - 1) / 2))%DIV;
}

void getInv() {
	int i;
	facInv[MAX] = getInvN(fac[2000002], DIV - 2);
	for (i=MAX-1; i > 0; i--) {
		facInv[i] = ((i + 1) * facInv[i + 1])%DIV;
	}
}

int getBinary(int x, int y) {
	return (fac[x + y + 2] * ((facInv[x + 1] * facInv[y + 1])%DIV))%DIV;
}

int main(int argc, char** argv)
{
	int T, test_case;
	 // freopen("input.txt", "r", stdin);

	int i, b1 = 1, b2 = 1;
	long long top=1;
	for (i = 1; i <= MAX; i++) {
		fac[i]=(top=(top*i) % DIV);
	}
	getInv();

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{

		Answer = 0;
		 // Print the answer to standard output(screen).
		int n, m;
		cin >> n >> m;	
		Answer = getBinary(n, m)-1;
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;//Your program should return 0 on normal termination.
}