[백준] 11051번 : 이항 계수2 Silver2(실버2) - JAVA[자바]

[Silver II] 이항 계수 2 - 11051

문제 링크

성능 요약

메모리: 12904 KB, 시간: 108 ms

분류

조합론, 다이나믹 프로그래밍, 수학

제출 일자

2023년 11월 8일 10:19:14

문제 설명

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

입력

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

출력

(NK)를 10,007로 나눈 나머지를 출력한다.

import java.util.Scanner;

class Main{ 
    public static final int DIV = 10007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int result = (factorial(n) * pow(factorial(m) * factorial(n-m) % DIV, DIV - 2)) % DIV;
        System.out.println(result);
    }
    private static int pow(int a, int p) {
        int ret = 1;
        while(p > 0){
            if(p%2!=0){
                ret *= a;
                p--;
                ret %= DIV;
            }
            a *= a;
            a %= DIV;
            p /= 2;
        }
        return ret;
    }
    private static int factorial(int n){
        if(n <= 1) return 1;
        return (n * factorial(n-1)) % DIV;
    }
}