[BOJ/PYTHON] 11401. 이항 계수 3

백준 문제 링크: https://www.acmicpc.net/problem/11401

문제 요약

이항 계수를 1,000,000,007로 나눈 나머지

핵심 아이디어

팩토리얼의 경우 바텀업으로 for문을 돌려서 팩토리얼문을 구해두고, 페르마의 소정리를 이용해서 구해주면 된다.

풀이

# gold1-11401. 이항 계수 3

import sys
input = sys.stdin.readline

large = 1000000007
n, k = map(int, input().split())
factorial = [1 for _ in range(n+1)]

def square(a):
    a = a % large
    a = a * a
    return a % large

def binary_power(n, k):
    if k == 1:
        return n % large
    if k % 2 == 0:
        b = binary_power(n, k//2)
        return square(b)
    else: 
        b = binary_power(n, k//2)
        return (square(b) * (n % large)) % large

for i in range(2, n+1):
    factorial[i] = factorial[i-1] * i % large

# nCk 
# aCb
a = factorial[n]
b = (factorial[n-k] * factorial[k]) % large

# 페르마의 소정리 이용
# (A/B) % m     
# = A * B**(-1) % m 
# = A * B**(-1) * B**(m-1) % m 
# = A * B**(m-2) % m 
# = (A % m) * (B**(m-2) % m) % m 
print((a % large) * (binary_power(b, large-2) % large) % large)

실행 시간

메모리 191116KB, 시간 1152ms (python3)