Baekjoon 13977. 이항 계수와 쿼리 / Python

설명

이 코드는 이항 계수 (nr)\binom{n}{r}(rn​)를 효율적으로 계산하기 위한 방법을 사용하고 있습니다.

• 팩토리얼 계산은 사전에 미리 처리하여 빠르게 조회할 수 있도록 합니다.
• 역수는 페르마의 소정리(Fermat's Little Theorem)를 이용하여 ap−2mod  pa^{p-2} \mod pap−2modp로 계산합니다.
• 시간 복잡도:
  • 팩토리얼 계산: O(n)O(n)O(n)
  • 거듭제곱 계산: O(log⁡n)O(\log n)O(logn) (재귀 호출 방식)
  • 이 코드의 주요 시간 복잡도는 입력 크기에 비례하여 매우 효율적입니다.

import sys

# 1부터 4000000까지의 팩토리얼 값을 계산하여 저장하는 리스트
factorial = [1] * 4000001
for i in range(2, 4000001):
    # factorial[i]는 i! % 1000000007을 저장합니다.
    factorial[i] = factorial[i - 1] * i % 1000000007

# 큰 수의 거듭제곱을 계산하는 함수
def find(x, n):
    if n == 1:
        return x % 1000000007  # n이 1이면 x % 1000000007을 반환합니다.
    else:
        # n이 2 이상인 경우에는 n을 절반으로 나눈 후 재귀적으로 호출합니다.
        tmp = find(x, n // 2)
        if n % 2 == 0:
            # n이 짝수인 경우, (x^(n/2))^2을 계산합니다.
            return tmp * tmp % 1000000007
        else:
            # n이 홀수인 경우, (x^(n//2))^2 * x을 계산합니다.
            return tmp * tmp * x % 1000000007


m = int(sys.stdin.readline())


for _ in range(m):
    n, r = map(int, sys.stdin.readline().split())
    
    # nCr의 값을 계산합니다: n! / (r! * (n-r)!) % 1000000007
    # 먼저, n!을 factorial[n]에서 가져옵니다.
    # 그리고, r! * (n-r)!의 역수를 구하기 위해, r! * (n-r)!의 팩토리얼 값을 곱한 뒤 역수(mod 1000000007)로 나눕니다.
    # find() 함수를 사용하여 역수를 계산합니다.
    result = factorial[n] * find(factorial[r] * (factorial[n - r]), 1000000007 - 2) % 1000000007
    
    # 계산된 결과를 출력합니다.
    print(result)