[백준/11401/파이썬] 이항계수 3

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

11401번: 이항 계수 3

Problem

• 자연수 N과 정수 K가 주어졌을 때 이항 계수 C(N,K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에 N)과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

SOL

 

간단하면서도, 강렬한 문제이다. 이항계수는 nCk의 숫자를 나타내는 우리가 많이 봤던 그 삼각형 모양의 표라고 생각하면 된다. 보통, 이항 계수는 nCk = n-1Ck-1+n-1Ck 의 성질을 이용해서, DP 방법으로 많이 푼다. 

하지만 DP의 방법은 , O(N^2)이다.

 

이 문제는 O(N^2)도 허용하지 않는, 엄청난 최적화를 요구하는 문제이다.  O(N)내에서 해결해야한다.

그렇다면, nCk = N!/K!(N-K)!이고, factorial의 구현은 O(N)이면 충분하므로, nCk %P를 간단하게 구하면 될줄알았다.

하지만, 이 식에는 문제가 있다. mod 연산을 할 때, 나눗셈에는 분배 법칙이 성립되지 않는점이였다.

 

즉, N!%P / K!*(N-K)!%P  != (N!/K!(N-K)!)%P

예를 들어, (6/5)%5 = 1.xxxx이지만, (6%5)/(5%5) = 1/0 이 되버리기 때문에, 분모가 0이 될 가능성이 있기 때문에, 분배 법칙은 성립하지 않는다. 

 

그러므로, 우리는 , 나눗셈 식을 곱셈의 형식으로 나타내거나, 다른형태의 식으로 바꿔서 나타내야 한다.

이때, 이용되어 지는게 페르마(ㄷㄷ)의 소정리라고 한다.

 

페르마의 소정리에 의해, P가 소수이고 A가 P의 배수가 아니면,

 

A를 P로 나누었을 때, 나머지가 1이 된다는 소리이다. 예를들어, 64^70%71 = 1이다. 이것이 수학의 힘?

이 식의 유용함은 여기서 끝이 아니다.  수학에서의 "1"은 엄청난 의미를 가지고 있는 숫자다. 곱했을 때, 그대로인 숫자이고, 식 조작에도 엄청 유리한 숫자이다. (역시 페르마님..)

 

 

A는 0이 아니니까, 나눌 수 있다. 즉, 어떠한 A와 소수 P가 준비되어 있다면, 역원을 바로 구할 수 있는 엄청난 정리(?)

가 중요한게 아니고, 우리는 이 방법을 이항계수를 구하는데 이용할 것이다.

A= K!(N-k)!로 넣어버리면, 우리는 이제 (N!/K!(N-K)!)%P)을 구할 수 있게 된다.

N! %P *((K!%P*(N-K)!%P)^P-2)%P

거듭제곱을 빨리하려면, 분할정복을 이용하면 된다. 간단한 예시를 들면, 2^10 = 2^5*2^5 , 2^11=2^5*2^5*2 라는 개념을 이용하면 된다.

 

# 이항 계수
import sys
input= sys.stdin.readline
# 거듭제곱을 빠르게 하는 방법 
# divide Conquer
P=1000000007
N,K=map(int,input().split())

def DoC(a,b):
    if b==0:
        return 1
    if b%2:# 홀수이면
        return (DoC(a,b//2)**2*a)%P
    else:
        return (DoC(a,b//2)**2)%P
    
fct=[1 for _ in range(N+1)]

for i in range(2,N+1):
    fct[i] = (fct[i-1]*i)%P

B=(fct[K]*fct[N-K])%P
print(((fct[N]%P)*(DoC(B,P-2)%P))%P)