[SWEA] 5607. 조합

간단해보이는 문제지만 다양한 개념들이 사용된 문제이다. 다음과 같은 개념들이 사용되었다.

모듈러연산의 특징
모듈려는 /을 제외한 +, -, * 에 대해서 다음과 같은 특징을 가진다.
(a mod n + b mod n) mod n = (a + b) mod n
(a mod n - b mod n) mod n = (a - b) mod n
(a mod n * b mod n) mod n = (a * b) mod n

합동관계
두 a, b숫자가 n을 mod한 결과 값이 같다면 모듈러 합동관계라 한다.
즉, a mod n = b mod n의 관계를 a ≡ b (mod n)으로 표현할 수 있다.

페르마의 소정리
p가 소수이고 a가 p로 나누어지지 않는 정수이면 다음과 같은 특징을 가진다.
a^p ≡ a (mod p) 
a^p-1 ≡ 1 (mod p)
a^p-2 ≡ a^-1 (mod p)   

조합
Combination, 서로 다른 n개에서 r개를 뽑는 경우의 수이다.
nCr = n! / (n-r)! * r!
nCr = (n-1)C(r-1) + (n-1)Cr

거듭제곱의 분할정복
a^n 을 구할때 다음과 같이 구할 수 있다.
IF n%2==0, a^n = a^(n/2) * a^(n/2) = ...
IF n%2!=0, a^n = a * a^(n/2) * a^(n/2) = ...

문제로 돌아와 예로써 7C5 mod 13 을 해보기로 가정한다면, 위의 특징들을 사용하여 연산을 한다면 다음과 같다.
7C5 mod 13
= (7! mod 13 / (2! mod 13) * (5! mod 13)) mod 13 
= (7! mod 13 / 240 mod 13) mod 13
= (7! mod 13 / 6 mod 13) mod 13 이 된다.
이때 mod 연산은 / 엔 적용이 안되므로 1 / 6 을 분자로 올리는 과정이 필요한데, 페르마의 소정리 기법이 사용된다. 
즉, a^p-2 ≡ a^-1 (mod p) 을 이용하여 1 / 6 mod 13 이 6^(13-2) mod 13 으로 바뀌게 된다.
결론적으로 7C5 mod 13 = (7! mod 13 * 6^11 mod 13) mod 13 이 된다.
이때, 거듭제곱은 powCalc라는 함수를 이용하여 분할정복을 하는 과정을 거친다. 또한, 메모리를 줄이기 위해 factorial 함수를 구하는 과정을 전처리하여 모든 테스트케이스에 대해 한번만 수행되도록 하였다.

이와 같은 방식으로 문제를 해결하면 풀리는 문제이다. 기본적으로 수학적 특징에 대해 알고 있어야 풀 수 있는 문제이다.

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution_d3_5607_조합 {
    static int mod = 1234567891;
    static int N;
    static long[] factorial;
    
    static int R;
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T=Integer.parseInt(br.readLine());
        factorial=new long[1000000+1];
        factorial[0]=1;
        for(int i=1;i<=1000000;i++)
            factorial[i]=(factorial[i-1]*i)%mod;        //factorial 초기화
        
        for(int tc=1;tc<=T;tc++) {
            st= new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            R=Integer.parseInt(st.nextToken());
            
            
            long top = factorial[N]%mod;
            long bottom = ((factorial[N-R]%mod ) * (factorial[R]%mod))%mod;
            
            long moveToTop = powCalc(bottom,mod-2);
            
            System.out.println("#" +tc+" "+((top*moveToTop)%mod));
        }
    }
    
    static long powCalc(long num,int p) {
        if(p==0)
            return 1;
        
        long half = powCalc(num, p/2);
        
        if(p%2==0) {
            return ((half%mod) * (half%mod))%mod;
        }else
            return (((half*num)%mod) * (half%mod))%mod;
    }
}