[백준]11401 이항 계수 3, python

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

11401번: 이항 계수 3

 

nCk = n! / {(n-k)! * k!} (mod bignum)이다

곱셉에선 모듈로 연산이 각각 들어가도 되었지만 나눗셈도 가능한지 몰랐다.

그래서 구글링을 했고 페르마의 소정리라는 것을 알게 되었다.

모듈로 연산에 쓰이는 값이 소수인경우 곱셉의 역원으로 b^-1 (mod pn) = b^(pn-2) (mod pn)가 된다.

1,000,000,007 이란 값은 소수이므로(이것도 구글링해봤다.) nCk 또한 페르마 소정리를 사용하여 곱하기만 나타낼수 있다.

nCk = n! / {(n-k)! * k!} (mod M) =  n! / {(n-k)! * k!} * ((n-k)! *k!)^p-1 (mod M) = n! * ((n-k)! * k!)^(p-2) (mod M)

= [(n! % M) * {(n - k)! % M}^(p-2) * (k! % M)^(p-2)] % M

계산으로 나온 마지막 값을 분할 정복으로 풀면 해결된다.

fact_mod = None
M = 1_000_000_007

def pow_mod(number, k):
    if 0 == k:
        return 1
    x = pow_mod(number, k >> 1)
    if k & 1:   # odd
        return (x * x * number) % M
    else:       # even
        return (x * x) % M

def find_binomial_coefficient(N, K):
    nfacto = fact_mod[N]
    nkfacto = fact_mod[N - K]
    kfacto = fact_mod[K]
    reverse_nkf = pow_mod(nkfacto, M - 2)
    reverse_kf = pow_mod(kfacto, M - 2)
    ret = (nfacto * reverse_nkf * reverse_kf) % M
    return ret

def main():
    N, K = map(int, input().split())
    global fact_mod
    fact_mod = [1 for _ in range(N + 1)]
    for i in range(2, N + 1):
        fact_mod[i] = (fact_mod[i - 1] * i) % M
    print(find_binomial_coefficient(N, K))

if __name__ == "__main__":
    main()

 

오랜만에 분할정복 문제를 풀어봤는데 factorial이나 pow같은 제곱 계산은 풀만했다.

단지 페르마의 소정리를 몰라서 오래 걸렸다 

C++은 중간과정에 있는 값들을 long long 자료형으로 사용하면 똑같이 해도 될거라 생각한다.

---

참고한 글

https://ohgym.tistory.com/13

모듈러 나눗셈