[백준] 11401번 : 이항 계수 3 Gold1(골드1) - JAVA[자바]

[Gold I] 이항 계수 3 - 11401

문제 링크

성능 요약

메모리: 12920 KB, 시간: 152 ms

분류

조합론, 분할 정복을 이용한 거듭제곱, 페르마의 소정리, 수학, 모듈로 곱셈 역원, 정수론

제출 일자

2023년 11월 8일 10:59:52

문제 설명

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

출력

(N K)를 1,000,000,007로 나눈 나머지를 출력한다.

import java.util.Scanner;

class Main{ 
    public static final long DIV = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long k = sc.nextInt();
        
        long numer = factorial(n);
        long denom = factorial(k) * factorial(n - k) % DIV;

        System.out.println(numer * pow(denom, DIV - 2) % DIV);
    }

    private static long pow(long base, long expo) {
        long ret = 1;
        while(expo > 0){
            if(expo % 2 == 1){
                ret = (ret * base) % DIV;
                expo--;
            }
            base *= base;
            base %= DIV;
            expo /= 2;
        }
        return ret;
    }
    
    private static long factorial(long n){
        long fac = 1L;
        for(long i = 1; i <= n; i++){
            fac *= i;
            fac %= DIV;
        }
        return fac;
    }
}