이항 계수 3 (11401번) - 백준 (BOJ)

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

11401번: 이항 계수 3

 

 

백준 - 이항 계수 3 (11401번)

 

난이도 : Gold 1

알고리즘&자료구조 : Mathematics (수학) & Fertmat's little Theorem (페르마의 소정리) & Exponentiation by Squaring (빠른 거듭제곱)

 

---

 

페르마의 소정리를 알아야 풀 수 있는 문제이다.

 

 

 

< 전체 코드 >

def factorial(s, e, val, mod):
    for i in range(s, e):
        val = (val * i) % mod
    return val


class BiCoeffcient():
    def __init__(self, N, K):
        K = min(N, N-K)
        mod = 1_000_000_007

        fac_k = factorial(1, K+1, 1, mod)
        fac_nk = factorial(K+1, N-K+1, fac_k, mod)
        fac_n = factorial(N-K+1, N+1, fac_nk, mod)
        
        mul = (fac_k * fac_nk) % mod
        cur = 1
        for i in map(int, bin(1_000_000_005)[-1:1:-1]):
            if i:
                cur = (cur * mul) % mod
            mul = (mul * mul) % mod
        self.answer = (fac_n * cur) % mod


if __name__ == '__main__':
    bincoff = BiCoeffcient(*map(int, input().split()))
    print(bincoff.answer)

 

 

---

 

① N! , (N-K)! , K! 을 모두 구한다.

def factorial(s, e, val, mod):
    for i in range(s, e):
        val = (val * i) % mod
    return val


fac_k = factorial(1, K+1, 1, mod)
fac_nk = factorial(K+1, N-K+1, fac_k, mod)
fac_n = factorial(N-K+1, N+1, fac_nk, mod)

 

 

 

② [ N! * (N-K)! ] ^ (1_000_000_007 - 2) 을 계산한다. (페르마의 소정리)

 

(p = 1000000007) 은 소수이므로, 페르마의 소정리를 적용할 수 있다.

 

빠른 거듭제곱 방법을 활용하면, log(N) 의 시간복잡도로 계산할 수 있다. (Exponentiation by Squaring)

 

숫자가 너무 커지지 않게, 중간중간 mod = 1_000_000_007 로 잘 나눠준다.

mul = (fac_k * fac_nk) % mod
cur = 1
for i in map(int, bin(1_000_000_005)[-1:1:-1]):
    if i:
        cur = (cur * mul) % mod
    mul = (mul * mul) % mod

 

 

 

③ 위의 ②에서 구한 cur 값에 N! 값을 곱해주고, mod로 나눈 나머지를 구한다.

그 나머지 값이 정답이 된다.

self.answer = (fac_n * cur) % mod