[JAVA] 백준 11051 - 이항 계수2

https://www.acmicpc.net/problem/11051

이항 계수 (N,K)를 10,007로 나눈 나머지를 구하는 문제이다.

이항 계수(N,K)란 nCk를 의미하고 이는 곧 N!/K!*(N-K)!를 의미하며 이것은 N! * (K!*(N-K)!)^-1이다.

따라서 문제에서 요구하는 것은 N! * (K!*(N-K)!)^-1 % 10007이다.

문제는 이제 (K!*(N-K)!)의 p에 대한 모듈러 역원을 구해야 하는데, 모듈러 역원이란 a * x ≡ 1 mod p 로 표시하고 이는 어떤 값 x에 a를 곱했을 때 그 값을 p로 나눴을 때 나머지가 1인 수를 의미한다.

예를 들어 a=3이고 p가 7일 때 3의 7에 대한 모듈러 역원은 5이다. 3 * 5 /7 == 1이기 때문이다.

 

페르마의 소정리는 a !≡0 mod p이고 p가 소수일 경우 a^p-1 ≡ 1 mod p 라는 것을 의미한다.

이 식의 양변에 a^-1을 곱하면 a^p-2 ≡ a^-1 mod p가 되고 이것은 a^p-2%p 값을구하면 모듈러 연산의 역원을 구할 수 있다는 것이다.

 

따라서 이 문제에서는 a = K!*(N-K)! 이고 p는 10007이므로 K!*(N-K)!의 10005제곱을 10007로 나눈 나머지를 구한 뒤 N!을 10007로 나눈 나머지와 곱하면 구할 수 있다.

 

제곱은 빠른 제곱 알고리즘을 사용했고 매 연산마다 a를 제곱하고 지수의 첫번째 비트가 1일 경우에 결과값에 제곱한 a를 곱해주며 비트를 오른쪽 shift하는 알고리즘이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int mod = 10007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int n = info[0];
        int k = info[1];
        int ans = getFact(n);
        int ans2 = fastSquare(getFact(k)*getFact(n-k)%mod,10005);
        System.out.println(ans * ans2 % mod);
    }
    static int fastSquare(int a, int target){
        int result = 1;
        while(target!=0){
            if((target&1)==1){
                result = result * a % mod;
            }
            a = a * a % mod;
            target>>=1;
        }
        return result;
    }
    static int getFact(int n){
        if(n<=1) return 1;
        return n*getFact(n-1)%mod;
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }

}