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

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

https://ghcode.tistory.com/302

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

이항계수와 모듈러 역원을 복습하기 위해 풀어본 문제이다.

N의 범위와 Mod 값이 달라져서

팩토리얼을 재귀방식 -> DP로 바꿨고 long type으로 선언했다.

그 외에는 동일하다.

 

N의 범위가 10^18인 문제도 있는 것을 보니 팩토리얼을 구하는 여러가지 방법을 공부해야겠다. 

그 뒤엔 동적계획법 문제를 더 풀어보면 좋을 것 같다.

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[] info = getArray(br.readLine());
        int n = info[0];
        int k = info[1];
        dp[0] = 1;
        dp[1] = 1;
        long ans = getFact(n);
        long ans2 = fastSquare(getFact(k)*getFact(n-k)%mod,mod-2);
        System.out.println(ans * ans2 % mod);
    }
    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();
    }

}