[JAVA] 백준 13977 - 이항 계수와 쿼리

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

https://ghcode.tistory.com/304

[JAVA] 백준 11401 - 이항 계수 3

이항 계수 3 문제를 M개의 testcase를 주고 해결하는 문제이다.

 

동일한 구현(dp 팩토리얼 + 빠른 제곱)으로 풀었더니 통과했다.

인생 첫 플레티넘 문제인데 공짜로 얻은 듯한 느낌이다.

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

public class Main {
    static int mod = 1000000007;
    static long[] dp = new long[4000001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = par(br.readLine());
        dp[0] = 1;
        dp[1] = 1;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tc; i++) {
            int[] info = getArray(br.readLine());
            int n = info[0];
            int k = info[1];
            long ans = getFact(n);
            long ans2 = fastSquare(getFact(k)*getFact(n-k)%mod,mod-2);
           sb.append(ans * ans2 % mod);
           if (i!=tc-1) sb.append("\n");
        }
        System.out.println(sb);
    }
    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();
    }

}