[백준 13977번] 이항계수와 쿼리 (Python3)

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를 풀었다면 어려울건 하나도 없는 문제.

 

 

오늘의 교훈) 전처리를 해야하는지 잘 살펴보자