[Baekjoon] 11401: 이항 계수 3
글 작성자: SeoArc
문제

간단히 이항계수 (n k)를 구하는 문제이다.
풀이
대표 풀이
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q11401 { public static final int MOD = 1000000007; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nk = br.readLine().split(" "); int n = Integer.parseInt(nk[0]); int k = Integer.parseInt(nk[1]); long nTotal = 1; for (int i = n; i > 0; i--) { nTotal *= i; nTotal %= MOD; } long kTotal = 1; for (int i = k; i > 0; i--) { kTotal *= i; kTotal %= MOD; } for (int i = n - k; i > 0; i--) { kTotal *= i; kTotal %= MOD; } long answer = 1; long x = kTotal; long y = MOD - 2; while (y > 0) { if (y % 2 != 0) { answer *= x; answer %= MOD; } x *= x; x %= MOD; y /= 2; } System.out.println((nTotal * (answer % MOD)) % MOD); } }
이 문제는 n! / k! * (n-k)! 을 모듈러 연산하여 구할 수 있다.
근데 여기서 나머지의 모듈러 연산은 역원을 구해야하기 때문에 페르마의 소정리를 이용해야한다.
즉 a/b (mod m)은 a (mod m) * b^(-1) (mod m) 인데 b^(-1)는 b의 역원을 뜻한다.
단, 페르마의 소정리를 사용할 경우에는 m의 값이 소수여야 한다.
여기선 m이 1000000007로 소수이기 때문에, 페르마의 소정리를 통해 구할 수 있다.
과정은 다음과 같다.
- m이 소수이고, a와 m이 서로소라면, a^(m-1)은 1을 모듈러 취한 것과 동치이다. 즉, a^(m-1) ≡ 1 (mod m) 이다.
- 따라서 a^(m-1) = a * a^(m-2) ≡ 1 (mod m)이 된다.
- a^(m-2)는 a * x ≡ 1 (mod m)을 만족하는 x가 되기 때문에, 역원은 a^(m-2)가 된다.
위 문제에선 n! / k!(n-k)! (mod m)를 구하면된다.
따라서 n! * (k!(n-k)!)^(m-2) (mod m)을 구하면 답이 나온다.
회고
페르마의 소정리와 분할정복을 통한 거듭제곱을 활용하여 푸는 문제이다.
이에 대한 개념이 충분하지 않아서 문제풀이에 어려움이 있었다.
좀 더 문제를 풀고 익숙해져야겠다.
'Algorithm > PS' 카테고리의 다른 글
[Baekjoon] 2176: 합리적인 이동경로 (0) | 2023.05.10 |
---|---|
[Baekjoon] 1943: 동전 분배 (0) | 2023.05.10 |
[Baekjoon] 1629: 곱셈 (0) | 2023.03.21 |
[Baekjoon] 6064: 카잉 달력 (0) | 2023.03.18 |
[Baekjoon] 17626: Four Squares (0) | 2023.03.17 |
댓글
이 글 공유하기
다른 글
-
[Baekjoon] 2176: 합리적인 이동경로
[Baekjoon] 2176: 합리적인 이동경로
2023.05.10 -
[Baekjoon] 1943: 동전 분배
[Baekjoon] 1943: 동전 분배
2023.05.10 -
[Baekjoon] 1629: 곱셈
[Baekjoon] 1629: 곱셈
2023.03.21 -
[Baekjoon] 6064: 카잉 달력
[Baekjoon] 6064: 카잉 달력
2023.03.18
댓글을 사용할 수 없습니다.