import sys
input = sys.stdin.readline
mod = 1000000007
def cal(x,n):
if n == 1:
return x
cal2 = cal(x,n//2)
if n%2:
return cal2*cal2*x %mod
else:
return cal2*cal2 %mod
factorial = [1]
for i in range(1,4000001):
factorial.append(factorial[i-1]*i%mod)
M = int(input())
for _ in range(M):
N,K = map(int,input().split())
print(factorial[N]*cal((factorial[K]*factorial[N-K])%mod,mod-2)%mod)
이항계수 3 [백준 11401번] 이항 계수 3 (Python3) (tistory.com) 문제에서 약간 업그레이드된 문제이다.
이항계수 3와 풀이방식은 완전히 똑같은데, 10만개의 쿼리에 대해서 결과를 내야 하므로 전처리 과정이 필요하다.
팩토리얼 값을 1~4000000 까지 저장해둔 뒤, 이항 계수 3의 방식대로 페르마의 소정리를 활용, mod 연산으로 결과값을 출력하면 된다.
이항계수3를 풀었다면 어려울건 하나도 없는 문제.
오늘의 교훈) 전처리를 해야하는지 잘 살펴보자