[BOJ 13977, Python 3] 이항 계수와 쿼리

 

 

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

13977번: 이항 계수와 쿼리

 

참조

다양한 방법의 이항계수 알고리즘 : https://koosaga.com/63

이항계수 (nCr) mod p 계산하기

 

 

페르마의 소정리 증명 : https://youtu.be/uhXOkoXtULI

 

$O(nlogp)$가 걸리는 이항계수 알고리즘 : https://velog.io/@gidskql6671/%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98-%EC%86%8C%EC%A0%95%EB%A6%AC

이항 계수 알고리즘 - Dynamic Programming, 페르마의 소정리

 

 

풀이

페르마의 소정리와 빠른 거듭제곱 알고리즘을 사용하여 $O(nlogp))$ 시간이 걸리는 이항계수 알고리즘을 사용하면 됩니다.

 

주의할 점은 팩토리얼 값을 미리 계산해둬야 시간 초과를 피할 수 있습니다.

 

코드

input = __import__('sys').stdin.readline
MOD = int(1e9 + 7)
N = 4 * int(1e6) + 1
factorial = [1] * N
for i in range(1, N):
    factorial[i] = (factorial[i-1] * i) % MOD
 
for _ in range(int(input())):
    n, k = map(int, input().split())
 
    A = factorial[n]
    B = (factorial[k] * factorial[n - k]) % MOD
 
    B2 = 1
    expo = MOD - 2
    while expo:
        if expo % 2: B2 = (B * B2) % MOD
        B = (B * B) % MOD
        expo //= 2
 
    res = (A * B2) % MOD
    print(res)