[파이썬 | BOJ | 11401] 이항 계수 3

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수

 

를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

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

 

출력

 

를 1,000,000,007로 나눈 나머지를 출력한다.

 

풀이

 

를 구하는 기본적인 다이나믹 프로그래밍 방법은 

 

로 정의되는 성질을 이용해서 푸는것이다.

 

하지만 이 문제에서 N의 제한이 매우크기 때문에 O(N^2)의 알고리즘으로는 시간초과가 걸리게된다.

 

이 문제를 해결하는 방법은

 

를 이용해서, 실제로 계산하는 것인데, 이 문제에서 1,000,000,007로 계속해서 나눠야 하는데, 분수꼴은 나머지 정리로 인해서 분자와 분모에다가 모두 나머지를 구해서 계산하게 되면 0으로 나누는 문제가 발생할 수 있기 때문에, 분수꼴을 곱셈꼴로 바꿔야 한다. 

 

이때 페르마의 소정리라는 것이 사용되는데, a^(p-1) ≡ 1 (mod p) 임을 이용해서

 

라고 표현할 수 있다.

 

이때 팩토리얼 계산을 미리 해놓는다고 하면, O(N + lgN) 으로 계산할 수 있다. (지수의 O(lgN) 알고리즘 사용)

따라서 시간내에 해결 할 수 있다.

 

지수의 O(lgN) 알고리즘은 이분 탐색을 이용한 방법을 사용하면 된다.