[JAVA] 백준 11402 - 이항 계수 4

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

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

일반적으로 N!*(K!*(N-K)!)^M-2를 구해 문제를 푸는데 N의 범위가 10^18이다.

페르마의 소정리와 DP 팩토리얼만 이용했다간 팩토리얼 구하는 부분에서 문제가 터질 것이다.

따라서 루카의 정리를 이용해 문제를 풀었다.

 

루카의 정리란, 

이항 계수 (N,K)를 M으로 나눈 나머지를 구할 때, N과 K를 M진법으로 나타낸 수의 각 자릿수(N1,K1)의 이항계수를 M으로 나눈 나머지를 누적해 곱하면 (N,K)를 M으로 나눈 나머지와 같다는 정리이다.

 

루카 페르마 이놈들은 천재가 틀림없다.

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

public class Main {
    static int mod= -1;
    static long[] dp = new long[2001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dp[0] = 1;
        dp[1] = 1;
        long[] info = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        long n = info[0];
        long k = info[1];
        int p = (int) info[2];
        long a = 1;
        mod  = p;
        while(n!=0&&k!=0){
            int target1 = (int) (n%mod);
            int target2 = (int) (k%mod);
            if(target1<target2){
                a*=0;
                n/=mod;
                k/=mod;
                continue;
            }
            long ans = getFact(target1);
            long ans2 = fastSquare(getFact(target2)*getFact(target1-target2)%mod,mod-2);
            a = a * ans %mod * ans2 % mod;
            n/=mod;
            k/=mod;
        }
        System.out.println(a);
    }
    static long fastSquare(long a, int target){
        long result = 1;
        while(target!=0){
            if((target&1)==1){
                result = result * a % mod;
            }
            a = a * a % mod;
            target>>=1;
        }
        return result;
    }
    static long getFact(int n){
        if(dp[n]!=0) return dp[n];
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1]*i%mod;
        }
        return dp[n];
    }

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

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

}