백준 25569번: My뷰 꾸미기

https://www.acmicpc.net/problem/25569

25569번: My뷰 꾸미기

---

주어진 예제의 답이 왜 54인지 생각해보면 다음을 알 수 있습니다.

$$ 54 = \binom{1}{1}\binom{2}{1} \times \left ( \binom{3}{1}\binom{2}{1} + \binom{3}{2}\binom{2}{2} \right ) \times \binom{1}{1}\binom{3}{1} $$

 

이를 이해했다면 문제의 답을 $N$, $A_{i}$, $B_{i}$에 대해 일반화할 수 있습니다.

 

$$ \textrm{Answer} = \prod_{i=1}^{N} \sum_{k=1}^{ \textrm{min} \left ( A_{i} , B_{i} \right ) } \binom{A_{i}}{k} \binom{B_{i}}{k} $$

 

이제 이걸 $10^{9}+7$으로 나눈 나머지를 출력하려는데, $N$, $A_{i}$, $B_{i}$의 크기가 걸립니다.

 

위 식의 복잡도는, $\binom{n}{k}$가 $O \left ( 1 \right )$에 주어진다고 해도 여전히 $O \left ( 300000 \times N \right )$ 입니다.

(모든 $ \textrm{min} \left ( A_{i}, B_{i} \right ) = 300000$ 인 경우)

 

제한 시간이 1초이므로, 최소한 $O \left ( N \right )$ 수준은 되어야 할 것 같습니다.

 

이때 다음 성질을 활용할 수 있습니다.

$$ \sum_{k=1}^{ \textrm{min} \left ( A_{i} , B_{i} \right ) } \binom{A_{i}}{k} \binom{B_{i}}{k} = \binom{A_{i}+B_{i}}{A_{i}} - 1 $$

이는 Vandermonde's Identity라고 부르는 성질입니다.

https://en.wikipedia.org/wiki/Vandermonde%27s_identity

 

(링크에서의 $r$이 $ \textrm{min} \left ( A_{i}, B_{i} \right )$ 인데, 어차피 $\binom{A_{i}+B_{i}}{\textrm{min} \left ( A_{i}, B_{i} \right )} = \binom{A_{i}+B_{i}}{A_{i}} = \binom{A_{i}+B_{i}}{B_{i}}$ 입니다.)

 

이제 전처리를 통해 각 이항계수가 $O \left ( 1 \right )$에 주어진다면, 전체 문제가 $O \left ( N \right )$에 풀림을 알 수 있습니다.

$$ \textrm{Answer} = \prod_{i=1}^{N} \binom{A_{i}+B_{i}}{A_{i}} $$

 

다음은 제 코드입니다.

#include <stdio.h>
#include <stdlib.h>
#define mod 1000000007

long long power_modular (long long x, long long y);

long long factorial[600001];
long long factorial_inverse[300001];

int main() {
	
	factorial[0] = factorial[1] = 1;
	for (int i = 2; i <= 600000; i++) {
		factorial[i] = factorial[i-1] * i % mod;
	}
    factorial_inverse[300000] = power_modular(factorial[300000], mod - 2);
    for (int i = 299999; i >= 0; i--) {
        factorial_inverse[i] = factorial_inverse[i+1] * (i+1) % mod;
    }
	
	int N;
	scanf("%d", &N);
	
	long long answer = 1;
	while(N--)
	{
        int A, B;
        scanf("%d %d", &A, &B);
		long long temp = factorial[A+B] *
						(factorial_inverse[A] * factorial_inverse[B] % mod) % mod;
		answer = answer * (temp - 1) % mod;
	}
	printf("%lld", answer);
	
	return 0;
}

long long power_modular (long long x, long long y) {
	long long result = 1;
	while (y) {
		if (y & 1) {
			result = result * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return result;
}

(C11, 124ms, 8148KB, 제출번호 53706713)

---

 

Lucas' theorem의 경우 mod가 너무 커서 부적합합니다. 즉, 전처리를 하는 게 훨씬 편리합니다.

 

이항계수를 구하는 테크닉 중 파스칼 삼각형은 복잡도가 $O \left ( nk \right )$ 이라 부적합합니다.

저의 경우는 [BOJ13997]을 사용하였습니다.

또는 [BOJ11401] 등을 사용하여도 전처리를 $O \left ( N \right )$에 하는 건 동일하므로 무방합니다.