문제
자연수 N과 정수 K가 주어졌을 때 이항 계수 \binom{N}{K}를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)
출력
\binom{N}{K}를 1,000,000,007로 나눈 나머지를 출력한다.
아이디어 1 : 실패
개요
- 파스칼의 정리 이용
- 재귀함수를 이용하기
코드
python
""" 이항계수 3 """
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100)
big = 1000000007
def binom(n, k):
if k == 1:
return n
elif n == k:
return 1
else:
return (binom(n-1, k-1) + binom(n-1, k)) % big
if __name__ == "__main__":
n, k = map(int, input().split())
ans = binom(n, k)
print(ans)
이 방법은 recursionerror로 실패
아이디어 2
- 수가 너무 커서 일단 계산을 해야 한다.
\dfrac{n!}{r!(n-r)!}
= n! \cdot \{r!(n-r)!\}^{-1}
\dfrac{n!}{r!(n-r)!} \mod x~
=~n!\cdot \{r!(n-r)!\}^{-1} \mod x
- 이럴 때 파스칼의 정리를 쓴다.
a^p \equiv a \pmod p
이게 무슨 상관이 있냐 할 텐데, 합동식의 성질을 생각해보면 다음과 같다.
a^{p-2} \equiv a^{1-2} \pmod p
- 파스칼의 소정리를 활용.
n! \mod x ~\cdot~
\{r!(n-r)!\}^{-1} \mod x
n! \mod x ~\cdot~
\{r!(n-r)!\}^{x-2} \mod x
코드
- 분자 파트 계산 : 팩토리얼 이용
- 분모 파트 계산 : 팩토리얼 ⇒ 거듭제곱
python
""" 이항계수 3 """
import sys
input = sys.stdin.readline
# 팩토리얼
def fac(n):
global p
x = 1
for i in range(2, n+1):
x = (x * i) % p
return x
# 거듭제곱
def square(n, k):
global p
if k == 0:
return 1
elif k == 1:
return n
temp = square(n, k//2)
if k % 2 == 0:
return temp * temp % p
else:
return temp * temp * n % p
if __name__ == "__main__":
n, k = map(int, input().split())
p = 1000000007
# 분모
top = fac(n)
# 분자
bottom = fac(k) * fac(n-k) % p
# 전체 계산
print( top * square(bottom, p-2) % p )