[Baekjoon] 11401: 이항 계수 3

문제

간단히 이항계수 (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로 소수이기 때문에, 페르마의 소정리를 통해 구할 수 있다.

과정은 다음과 같다.

 

1. m이 소수이고, a와 m이 서로소라면, a^(m-1)은 1을 모듈러 취한 것과 동치이다. 즉, a^(m-1) ≡ 1 (mod m) 이다.
2. 따라서 a^(m-1) = a * a^(m-2) ≡ 1 (mod m)이 된다.
3. 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)을 구하면 답이 나온다.

 

회고

페르마의 소정리와 분할정복을 통한 거듭제곱을 활용하여 푸는 문제이다.

이에 대한 개념이 충분하지 않아서 문제풀이에 어려움이 있었다.

좀 더 문제를 풀고 익숙해져야겠다.