[JAVA] SWEA 5607 - 조합

Solution

nCr = n! / ((n-r)!*r!)
문제에서는 nCr을 구해서 1234567891로 나눈 나머지를 구하는 것이다.
그런데 문제는 n이 최대 1000000이기 때문에 모듈러 연산을 이용하여야 하는데 나눗셈에서는 모듈러 연산을 사용할 수가 없다.

모듈러 연산 (+,-,*에서만 가능)
(a * b) % mod = (a%mod * b%mod) % mod

그래서 분모인 (n-r)!*r!를 분자로 올려줘야 하는데 이때 페르마 소정리가 이용된다.
페르마 소정리에 따르면 a^p-2%C = a^-1% C이다.
그래서 문제에서 구해야 하는 식
n! / ((n-r)!*r!) % 1234567891에서
A = n!, B = (n-r!)!*r!, C = 1234567891라고 하면
-> n! / ((n-r)!*r!) % 1234567891
-> A*B^-1% C
모듈러 연산을 적용하면
-> (A%C*B^-1% C)%C
여기서 페르마의 소정리를 이용하면
-> (A%C*B^C-2%C)%C

분수를 정수로 나타낼 수 있게 되었으므로 이제 A, B 값을 구하고 둘을 곱해서 답을 구하게 되는 과정에서 모듈러 연산을 사용해서 값을 구할 수 있게 된다.

Code

import java.util.*;
class Solution
{
    static final int MOD = 1234567891;
    static long factorial[] = new long[1000001];

	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
        StringBuffer sb = new StringBuffer();
        init();

        int T = sc.nextInt();
        for(int tc=1; tc<=T; tc++){
            int N = sc.nextInt();
            int K = sc.nextInt();

            long c1 = factorial[N];
            long c2 = (factorial[N-K] * factorial[K]) % MOD;
            long c3 = calculatePow(c2, MOD-2);

            sb.append("#").append(tc).append(" ");
            sb.append(c1 * c3 % MOD).append("\n");
        }
        System.out.println(sb);
    }
    //분할정복으로 구하면 O(logN)만에 구할수 있다.
    private static long calculatePow(long n, long k) {
        if(k == 1){
            return n;
        }
        long x = calculatePow(n, k/2) % MOD;
        if(k % 2 == 0){
            return x * x % MOD;
        }else{
            return ((x * x) % MOD * n) % MOD;
        }
    }

    private static void init() {
        factorial[0] = 1;
        for(int i=1; i<=1000000; i++){
            factorial[i] = factorial[i-1] * i % MOD;
        }
    }
}