BJ 13977 이항 계수와 쿼리

BJ 11041 이항 계수 3을 쿼리형으로 바꾸면 쉽게 풀 수 있습니다.

inverse의 시간복잡도가 $O(\log n)$이기 때문에 가능합니다.

코드

from sys import stdin, stdout

factorial = [1] * 4000001
for idx in range(2, 4000001):
    factorial[idx] = (factorial[idx-1] * idx) % 1000000007

def pow(n, k):
    if k == 1:
        return n
    pow_half = pow(n, k//2)
    if k % 2 == 0:
        return (pow_half ** 2) % 1000000007
    else:
        return (pow_half ** 2 * n) % 1000000007

def inverse(n):
    return pow(factorial[n], 1000000005)

m = int(input())
for _ in range(m):
    n, k = map(int, stdin.readline().split())
    stdout.write(str((factorial[n] * inverse(n-k) * inverse(k)) % 1000000007))
    stdout.write('\n')
stdout.flush()