[백준] 13977 - 이항 계수와 쿼리 (Python)

구하고 싶은 값은 $(n! / (n-k)!k!)\;mod\;P$ 가 된다.
n! 을 매번 구하는 것은 비효율적이므로 모든 경우의 팩토리얼 값을 미리 계산해 놓는다.

모듈러 연산에서 나눗셈은 곱셈 역원으로 바꾸어야 하므로 페르마의 소정리를 이용하면 $(n-k)!k!^{-1}\;mod\;P$ 와 동치가 되는 $(n-k)!k!^{P-2}\;mod\;P$를 구한다. 이 때 P가 매우 큰 수이므로 분할 정복을 이용해서 구해야 한다.

import sys
input = sys.stdin.readline

P = 10**9 + 7
m = int(input())

def div_sqr(a, x):
    if x == 1:
        return a
    if x % 2 == 0:
        return div_sqr(a, x//2)**2 % P
    else:
        return div_sqr(a, x-1)*a % P
        
factorial = [1]*(4*10**6+1)
for i in range(2, 4*10**6+1):
    factorial[i] = factorial[i-1]*i % P
    
for _ in range(m):
    n, k = map(int, input().rstrip().split())
    print(factorial[n]*div_sqr(factorial[n-k]*factorial[k]%P, P-2) % P)