7092 : 이항계수 (모듈러 역원)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
이항계수 C(n, k)를 구하는 프로그램을 작성하십시오.
이번에는 n이 최대 1,000,000으로 매우 큽니다.
팩토리얼과 페르마의 소정리를 이용한 모듈러 역원을 활용하여 C(n, k) mod 1,000,000,007을 구하십시오.
[제약 조건]
• $n, k$: $0 \le k \le n \le 1{,}000{,}000$
이번에는 n이 최대 1,000,000으로 매우 큽니다.
팩토리얼과 페르마의 소정리를 이용한 모듈러 역원을 활용하여 C(n, k) mod 1,000,000,007을 구하십시오.
[제약 조건]
• $n, k$: $0 \le k \le n \le 1{,}000{,}000$
입력 설명
첫째 줄에 두 정수 $n$과 $k$가 공백으로 구분되어 주어집니다. ($0 \le k \le n \le 1{,}000{,}000$)
출력 설명
$\binom{n}{k} \bmod (10^9+7)$을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10도움
C(n, k) = n! / (k! * (n-k)!) 입니다. 팩토리얼 배열과 그 역원 배열을 O(N)으로 전처리하여 풀이할 수 있습니다.