168. 1629(이항계수3) - 자바

import java.util.*;
import java.io.*;

class Main {
	static long P = 1000000007;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long N = sc.nextLong();
		long K = sc.nextLong();

		long A = factorial(N);
		long B = factorial(K) * factorial(N - K) % P;

		System.out.println(A * pow(B, P - 2) % P);
	}

	private static long pow(long base, long expo) {
		if (expo == 0) {
			return 1;
		}

		long tmp = pow(base, expo / 2);

		if (expo % 2 == 1) {
			return (tmp * tmp % P) * base % P;
		} else {
			return tmp * tmp % P;
		}
	}

	private static long factorial(long N) {
		long f = 1;

		while (N > 1) {
			f = (f * N) % P;
			N--;
		}

		return f;
	}
}

문제요약

숫자가 매우 큰 이항계수 정리를 진행하라.

설명

이번 문제 역시 수가 매우크기 때문에 그냥 이항계수 정리를 진행하면 시간초과가 발생할 수 밖에 없다.

여기서는 페르마의 정리가 이용된다.

페르마의 정리란 아래와 같다.

출처 : https://sangwoo0727.github.io/algorithm/Algorithm-BOJ11401/

정리하면 나눠지지 않는 수 즉 a가 p의 배수가 아닐때 다음과 같은 식으로 나타낼 수 있다는 것이다.

출처 : https://st-lab.tistory.com/241

이항정리는 위와같은 식이므로 페르마의 정리를 이용하면

 다음과 같이 구할 수 있다.

 

위식이 2번과 같이 될 수 있는 이유는 곱셈 분배법칙에 의한 것이다.

(K! (N-K)!)1000000007-2식이 왜 나왔는지 궁금할 수 있다.

이식은 역원에 대한 식이다.

즉, a (mod p) 에 대한 역원은 ap-2 (mod p)

먼저 (K! (N-K)!)1000000007-2은 거듭제곱과 같은 것으로 우리는 https://smhope.tistory.com/441 에서 아래의 메소드를 이용해서 풀었다.

	private static long pow(long base, long expo) {
		if (expo == 0) {
			return 1;
		}

		long tmp = pow(base, expo / 2);

		if (expo % 2 == 1) {
			return (tmp * tmp % P) * base % P;
		} else {
			return tmp * tmp % P;
		}
	}

그리고 팩토리얼을 사용했다. 팩토리얼은 재귀함수를 사용하면 다음과 같은 메소드로 나타낼 수 있다.

	private static long factorial(long N) {
		long f = 1;

		while (N > 1) {
			f = (f * N) % P;
			N--;
		}

		return f;
	}

메소드를 정의했으면 하나하나 풀면된다.

먼저 우리가 최종적으로 구해야 하는 식이다.

이 식을 파이썬을 이용해서 만들어 보면,

# 분자 N!
		long A = factorial(N);

# 분모 (K! * (N-K)!) mod p
		long B = factorial(K) * factorial(N - K) % P;

결국 

이 부분이

A * pow(B, P - 2)

이 부분으로 된다.

최종적으로는 

		System.out.println(A * pow(B, P - 2) % P);

이 식이 위와 같게 된다.