졍's 기술 블로그

이항 계수 2

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론

문제

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

출력

\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다.

예제 입출력

Algorithm

1. N * ... * 1을 총 K번 진행
2. K! 계산
3. 1번의 결과를 2번의 결과로 나눔
4. 3번의 결과를 10007로 나눈 나머지 출력

Code

import sys
sys.setrecursionlimit(10 ** 6)

# Factorial 계산하는 함수
def factorial(K):
    if K < 2:
        return 1
    else:
        return K*factorial(K-1)
    
# 입력
N, K = map(int, input().split())

# N * N-1 * ...
num1 = 1
for i in range(K):
    num1 *= N-i
    
# K!
num2 = factorial(K)

# (N * N-1 * ... // K!) % 10007
print((num1 // num2) % 10007)

메모리: 31324 KB
시간: 72 ms