조합의 곱의 합을 구하는 Vandermonde's identity

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

Vandermonde's identity - Wikipedia

 

1. Vandermonde's identity

 

음이 아닌 정수 m,n,r에 대하여, 다음 등식이 성립한다.

 

$$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k}$$

 

증명은 double counting 방법으로 해보면..

 

m명의 남자와 n명의 여자가 있을때, r명의 사람을 뽑는 방법은... $\binom{m+n}{r}$

 

그런데 다르게 생각하면 모든 k = 0,1,2,...,r에 대하여...

 

남자를 m명에서 k명을 뽑고, 여자를 n명에서 r-k명을 뽑는 방법의 합 $\sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k}$와 같다.

 

 

2. 연습문제

 

25823번: 조합의 합의 합 (acmicpc.net)

25823번: 조합의 합의 합

 

 

3. 풀이

 

다음이 성립하는것은 사실 매우 유명한 등식중 하나다

 

$$\sum_{k = 0}^{n} \binom{n}{k}^{2} = \binom{2n}{n}$$

 

위의 Vandermonde's identity에서 m = n이고 r = n일때 정확히 성립한다

 

그러므로 $$\sum_{n = 3}^{M} \sum_{k = 0}{n} \binom{n}{k}^{2} = \sum_{n = 3}^{M} \binom{2n}{n}$$ 으로 고친다.

 

그러면 $\binom{2n}{n}$을 $10^{9} + 7$로 나눈 나머지를 구한다.

 

$10^{9} + 7$은 유명한 소수 중 하나이다.

 

https://deepdata.tistory.com/370

이항계수를 구하는 알고리즘 고급편 - 페르마의 소정리-

 

m제한이 20만이라 m!*m!하더라도 $4*10^{10}$까지라 $10^{9} + 7$과 서로소

 

그러므로 페르마의 소정리에 의해... $p = 10^{9} + 7$이라고 한다면...

 

$$\sum_{n = 3}^{M} \binom{2n}{n} ≡ \sum_{n = 3}^{M} (2n)!(n!*n!)^{p-2} (mod p)$$

 

따라서, (2M)!까지 모두 구하는데 매번 $10^{9}+7$로 나눠줘야한다.

 

그리고 분할정복을 이용한 거듭제곱으로 $(n!*n!)^{p-2}$를 빠르게 구한다.

 

그리고 매번 누적할때마다 $10^{9} + 7$로 나눠줘야 시간이 빨라짐

 

mod = 10**9+7

m = int(input())

factorial = [0]*(2*m+1)

factorial[0] = 1

for i in range(1,2*m+1):
    
    factorial[i] = factorial[i-1] * i
    factorial[i] %= mod

answer = 0

for n in range(3,m+1):
    
    answer += factorial[2*n]*pow(factorial[n]*factorial[n], mod-2, mod)

    answer %= mod

print(answer)