[Divide & Conquer] 백준 이항계수3 11401 python3 풀이

 

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

문제

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

입력

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

출력

를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1
5 2
예제 출력 1
10

 

** 풀이: 페르마의 소정리 필요(다른것은 필요없음)

N, K = map(int, "4 4".split())
R = N - K
if (R > K): 
    R, K = K, R
C = 1_000_000_007
B = 1_000_000_005
def mul(X, Y): 
    return ((X%C) * (Y%C))%C
def process(k): 
    if (k in memos.keys()):
        return memos[k]
    q = int(k / 2)
    data = mul(process(q), process(k-q))
    memos[k] = data
    return data

def factorial(K):
    total = 1
    while (K > 0):
        total = (total * K) % C
        K = K - 1
    return total
        
A = (factorial(R) * factorial(K))%C
memos = {1:A}
print((factorial(N) * process(B)) % C)

 

# factorial을 미리 구했지만. 메모리와 시간은 더 오래 걸림. ㅠ
N, K = map(int, "4000000 2000000".split())
R = N - K
if (R > K): 
    R, K = K, R
C = 1_000_000_007
B = 1_000_000_005
def runFactorial(N):
    global factorials
    for i in range(2, N+1):
        factorials[i] = (i * factorials[i-1])%C
        
def mul(X, Y): 
    return ((X%C) * (Y%C))%C
def process(k): 
    if (k in memos.keys()):
        return memos[k]
    q = int(k / 2)
    data = mul(process(q), process(k-q))
    memos[k] = data
    return data

factorials = [0 for i in range(N+1)]
factorials[0], factorials[1] = 1, 1
runFactorial(N)

A = (factorials[R] * factorials[K])%C
memos = {1:A}

print((factorials[N] * process(B)) % C)