https://www.acmicpc.net/problem/11401
문제
자연수 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) 알고리즘은 이분 탐색을 이용한 방법을 사용하면 된다.
'알고리즘' 카테고리의 다른 글
[파이썬 | BOJ | 1756] 피자 굽기 (0) | 2020.06.03 |
---|---|
[파이썬 | BOJ | 9202] Boggle (0) | 2020.05.19 |
[파이썬 | BOJ | 2749] 피보나치 수 3 (0) | 2020.05.18 |
[파이썬 | BOJ | 6549] 히스토그램에서 가장 큰 직사각형 (0) | 2020.05.18 |
[파이썬 | BOJ | 1374] 강의실 (0) | 2020.05.16 |