https://www.acmicpc.net/problem/11401
11401번: 이항 계수 3
자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.
https://rudalsd.tistory.com/61?category=1064608
[ 알고리즘 ] 페르마의 소정리(Fermat's little theorem)
페르마의 소정리(Fermat's little theorem)는 다음과 같이 정리할 수 있습니다. $a\geq 0$에 대하여 $a^{p}\equiv a($mod $p)$를 만족하고, 만약 $p$가 소수이고, $a$와 $p$가 서로소이면 $a^{p-1}\equiv 1($mod $p)$를 만족
rudalsd.tistory.com
1. 먼저 $\binom{N}{K}$는 다음과 같이 나타낼 수 있습니다.
$\binom{N}{K} = \frac{N!}{(N-K)!K!}$
2. 페르마의 소정리를 이용하여 mod $m$에서 어떤 수를 $a$로 나눈다는 뜻은 $a$의 역원을 곱한다는 뜻과 같습니다. 따라서 $m$이 소수일 때, $a^{m-1}\equiv 1($mod $m)$이고, $a\times a^{m-2}\equiv 1($mod $m)$이므로 mod $m$에서 $a$에 대한 곱셈의 역원은 $a^{m-2}$입니다.
따라서,
$\frac{N!}{(N-K)!K!} \equiv N!\times ((N-K)!K!)^{m-2}($mod $m)$
이 됩니다.
3. 분모의 수로 나누는 방법 대신 $m-2$제곱한 값을 곱해주면 모듈러 연산 시 같은 결과가 나오는 것을 알 수 있습니다.
이때 $m$의 값이 $1,000,000,007$로 매우 크므로 분할 정복을 이용한 거듭제곱을 이용하여 문제를 풀어주면 됩니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<iostream> #define ll long long #define M 1000000007 using namespace std; ll Fac[4000001]; ll p(int n, int k) { if (k == 0) return 1; if (k == 1) return n; if (k % 2 == 0) { ll temp = p(n, k / 2); temp %= M; return (temp * temp) % M; } else { ll temp = p(n, k - 1); temp %= M; return (temp * n) % M; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, K; cin >> N >> K; Fac[0] = 1; Fac[1] = 1; for (int i = 2; i <= N; i++) { Fac[i] = Fac[i - 1] * i; Fac[i] %= M; } ll ans = Fac[N] * p((Fac[N - K] * Fac[K])%M, M - 2); ans %= M; cout << ans; } | cs |
'백준' 카테고리의 다른 글
| [ 백준 ] 1038번 - 감소하는 수 (C++) (0) | 2023.07.05 |
|---|---|
| [ 백준 ] 11402번 - 이항 계수 4 (C++) (0) | 2023.07.04 |
| [ 백준 ] 17025번 - Icy Perimeter (C++) (0) | 2023.07.01 |
| [ 백준 ] 8981번 - 입력숫자 (C++) (0) | 2023.06.30 |
| [ 백준 ] 1863번 - 스카이라인 쉬운거 (C++) (0) | 2023.06.29 |