[백준] #11401 이항계수3(Python)

자연수 N과 정수 K가 주어졌을 때 이항 계수 C(N,K)를 1,000,000,007로 
나눈 나머지를 구하는 프로그램을 작성하시오.

예제 입력 #1
5 2 #답 10

import sys

sys.stdin = open('./input.txt', 'r')

N, K = map(int, input().split())
p = 1000000007

arr = [[0 for _ in range(K+1)] for _ in range(N+1)]

def cef(N, K):
    if K == 0 or N==K:
        arr[N][K] = 1
    if K == 1:
        arr[N][K] = N
    
    if arr[N][K] == 0:
        arr[N][K] = cef(N-1, K) + cef(N-1, K-1)
    
    return arr[N][K]

ans = cef(N,K)
print(ans%p)

이런식으로 구현했지만 값이 10만 이상이 된다면 이 코드를 적용할 수 없음
따라서 페르마의 소정리를 따라야함

• 페르마의 소정리 이용
  

이런 개념을 적용시키면

import sys

sys.stdin = open('./input.txt', 'r')

N, K = map(int, sys.stdin.readline().split())
p = 1000000007

def factorial(N):
    n = 1
    for i in range(2, N+1):
        n = (n * i) % p 
    return n

def square(n, k):
    if k == 0:
        return 1
    if k == 1:
        return n
    
    tmp = square(n, k//2)
    
    if k % 2:
        return tmp * tmp * n % p
    else:
        return tmp * tmp % p
        
#페르마의 소정리와 식이 같음 n! * (r!(n-r)!)^p-2 % p
print(factorial(N) * square(factorial(N-K) * factorial(K) % p, p-2) % p)

계속해서 p를 나눠주는 이유 => 페르마의 소정리 적용했기 때문

• 오버플로우 방지: 모듈로 연산을 사용하면 계산 과정에서 발생할 수 있는 오버플로우를 방지할 수 있습니다. 오버플로우는 정수 값이 컴퓨터에서 사용할 수 있는 최대 범위를 넘어가는 경우 발생합니다. 이 경우, 결과는 잘못된 값이 될 수 있습니다. 모듈로 연산을 사용하면 모든 중간 결과가 p보다 작게 유지되므로, 오버플로우를 방지할 수 있습니다.
• 빠른 계산: 모듈로 연산을 사용하면 계산이 빠르게 진행됩니다. 큰 수를 다루는 경우 계산 속도가 느려질 수 있지만, 모듈로 연산을 사용하면 결과를 작은 범위로 유지하면서 계산할 수 있습니다. 이렇게 하면 계산 시간이 줄어들어 효율적인 처리가 가능합니다.
• 페르마의 소정리 적용: 페르마의 소정리를 적용하여 이항 계수를 계산하려면 모듈로 연산을 사용해야 합니다. 페르마의 소정리를 사용하여 팩토리얼의 역원을 구하고, 이를 이항 계수 공식에 적용하여 C(N, K)를 계산할 수 있습니다. 이를 위해서는 모든 계산 과정에서 p의 나머지 값을 구해야 합니다.
  출처 chatGPT