25823번 조합의 합의 합

들어가는 말

백준 두번째 글입니다.
이번 문제는 modulo를 활용하여 어떻게 나머지를 잘 구해낼 수 있을지에 대해 알아보고,
이항정리의 한 정리와 조합의 성질을 잘 엮어 문제를 풀어보겠습니다.

문제

입출력

풀이

문제 분석

본 문제는 조합 제곱의 합의 합을 구하는 문제입니다.

단순 조합의 합 $\sum {n\choose k} =2^n$임을 우리고 알고 있지만 제곱의 합은 생소한 편입니다.

저는 먼저 이항계수에 관한 정리를 검색해보았고 다음과 같은 정리를 얻을 수 있었습니다.

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

즉, 이항계수 제곱의 합은 ${2n\choose n}$ 이라고 할 수 있습니다.

그렇다면 우리는 이항계수 제곱의 합의 합은 $\sum_{n=3}^{n=M} {2n\choose n}$ 임을 단순히 알아낼 수 있겠군요.

이 수를 10^9+7로 나눈 나머지는 어떻게 알 수 있을까요?

그렇다면 먼저 정수론의 modulo에 대해 알 필요가 있습니다.

modulo 합동식

제 현대대수학 글에도 많이 언급되는 이 합동식을 정수론에서는 나머지에 관한 연산으로 다룹니다.

a$\equiv$b(mod m) 이라는 것은 a와 b를 m으로 나눈 나머지가 같다는 의미입니다.

예를 들어 a=5, b=3, m=2라면

1) 5를 2로 나눈 나머지는 1
2) 3을 2로 나눈 나머지도 1
이기 때문에
5 $\equiv$ 3 (mod 2)라고 할 수 있습니다.

이 때, a$\equiv$b(mod m), c$\equiv$d(mod m)라고 하면

1) a+c$\equiv$b+d(mod m)
2) a*c$\equiv$b*d(mod m)

이 성립함을 쉽게 증명할 수 있습니다.

즉, 서로 곱을 한 나머지도 같다는 것입니다.

modulo 나눗셈

그런데 나누기는 쉽지 않습니다. 우리가 잘 아는 나누기가 정수에서는 잘 정의되지 않기 때문입니다.

예를 들어 정수에서 4/2 = 2는 잘 정의되지만 4/3은 정수에 없기 때문입니다.

그러므로 우리는 정수에서 Divisible 즉, 나눌 수 있다 라는 표현을 사용합니다.

예를 들어 4|2는 4를 2가 나눌 수 있다 라는 의미입니다. 9|3, 100|5 도 각각 3이 9를 나눈다. 5가 100을 나눈다는 뜻입니다.

여기서 우리는 새로운 관점을 가질 수 있는데 나누어지는 수는 나누는 수의 배수라는 점을 사용합니다.

예를 들어, 100 = 5*20이죠. 이 때 5로 나눈다는 것은 5*20을 1*20으로 만드는 것입니다. 5를 없애는 것이죠.

이 concept을 modulo 합동식으로 가져옵시다.
modulo에서는 이 5를 없애는 것이 어렵지 않습니다.

Fermats little thm

이를 하기 위해서는 페르마의 소정리가 필요합니다.
페르마의 소정리의 _절대적으로 중요한 조건_은 소수로 나눌 때 성립한다는 겁니다.

페르마의 소정리는

If a ∤ p, then, $a^{p-1}≡1(mod\space p)$ (p는 소수)

이다.
해석해보면 어떤 a라는 숫자를 p-1 즉, 소수-1제곱 해주면 p로 나눈 나머지가 1과 같다는 것입니다.

예를 들어, p=3, a = 7이라고 하면 $7^2 ≡1(mod\space 3)$입니다.

이를 조금 변형해봅시다.

$a^{p-1}≡1(mod\space p)$ ⇔ $a *a^{p-2}≡1(mod\space p)$

이를 변형한 결과는 $a$에 $a^{p-2}$ 를 곱해주면 1과 같아진다는 의미입니다.

이는 우리가 원하는 결과인데

예를 들어 $100*5*5^{p-2}$을 p로 나눈 나머지는 $100*1$을 p로 나눈 나머지와 같다는 의미이기 때문입니다!

즉 우리는 어떤 수로 나눈 나머지를 알고 싶다면 그 수의 p-2제곱을 곱해주면 됩니다!

프로그래밍

제 문제 풀이 전략은 ${2n\choose n}$을 구하기 위해 ${2(n-1)\choose n-1}$ 를 이용하자는 전략입니다.

결국 DP입니다.

${2n\choose n}$과 ${2(n-1)\choose n-1}$은 다음과 같은 점화식을 따릅니다.

${2(n-1)\choose n-1}*(2n-1)$$*2n*{1\over n*n} = {2n\choose n}$

조합 식을 전개해보면 쉽게 알 수 있습니다.

우리는 $10^9+7$로 나눈 나머지를 구해야하는데 이 수는 소수입니다.

1. 2n-1과 2n을 곱한 나머지는 위에서 언급했듯 그냥 곱하고 $10^9+7$으로 나누어 주면 됩니다.
2. ${1\over n_n}$을 곱한 나머지는 페르마의 소정리를 이용하면 $(n_n)^{p-2}$를 곱한 나머지와 같습니다.

이 때 $(n*n)^{p-2}$를 구하는 시간복잡도는 O(log(p))입니다.

코드는 다음과 같습니다.

import math

mod = 10**9+7

def pow(n,p):
    if(p == 2):
        return (n**2)%mod
    if p%2==0:
        return pow((n**2)%mod,p//2)
    else:
        return(((n*pow(n,p-1))%mod))


sum_of_combination = 0

M = int(input())

#2C1로 cal 초기화
cal = 6

for n in range(3,M+1):
    cal = (cal*(2*n-1))%mod
    cal = (cal*(2*n))%mod
    cal = (cal*pow(n*n,mod-2))%mod
    sum_of_combination += cal

print(sum_of_combination%mod)