[백준, BOJ 11401] 이항 계수 3 (java)

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

11401번: 이항 계수 3

---

문제

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

입력

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

출력

$\binom{N}{K}$를 1,000,000,007로 나눈 나머지를 출력한다.

728x90

 

예제 입력 1

5 2

예제 출력 1

10

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static final long MOD = 1_000_000_007;
	
	private static long pow(long a, long n) {
		if(n == 0 || n == 1) {
			return a;
		}
		
		long tmp = pow(a, n / 2);
		
		long result = (tmp * tmp) % MOD;
		if((n & 1) == 1) result = (result * a) % MOD;
		
		return result;
	}

	public static void main(String[] args) throws Exception {
		

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		long N = Long.parseLong(st.nextToken());
		long K = Long.parseLong(st.nextToken());
		
		// (N! / (N - k)!) % MOD 구하기
		long result = 1;
		for (long i = N; i > N - K; i--) {
			result = (result * i) % MOD;
		}
		
		// K! 역원 구하기
		long tmp = 1;
		for (long i = 2; i <= K; i++) {
			tmp = (tmp * i) % MOD;
		}
		tmp = pow(tmp, MOD - 2);
		result = (result * tmp) % MOD;
		
		System.out.println(result);
	}

}