[알고리즘] Java / 백준 / 이항 계수 3 / 11401

[알고리즘] Java / 백준 / 이항 계수 3 / 11401

문제

문제 링크

접근 방식

나머지연산은 나눗셈에 대해 분배법칙이 성립하지 않는다.

(fac[n] / (fac[r]*fac[n-r])) % P != (fac[n]%P) / (fac[r]*fac[n-r]%P)

따라서 이를 위해 분모의 역원을 분자에 곱하는 방식으로 바꾼다

이 때 페르마의 소정리에 의해 (fac[r]fac[n-r])^-1 % P를 fac[r]fac[n-r]^(P-2)로 바꿀 수 있다.

fac[n] % P * (fac[r]*fac[n-r])^-1 % P 

fac[r]*fac[n-r]^-1 % P  == fac[r]*fac[n-r]^(P-2)

그리고 fac[r]*fac[n-r] ^(P-2)를 분할정복으로 제곱한다.

코드

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

public class Main_11401 {

	static final long P = 1000000007;
	public static void main(String[] args) throws IOException{
		BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
			
		int N = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
			
		System.out.println(nCr(N,R));
	}
	
	public static long nCr(int N, int R) {
		
		if(R == 0) return 1;
		if(R == 1) return N;
		
		// 팩토리얼 바텀업
		long fac[] = new long[N+1];
		fac[0] = 1;
		for(int i=1;i<=N;i++) {
			fac[i] = fac[i-1] * i % P;
		}
		
		// 분모 r!(n-r)! % p 를 페르마 소정리로 r!(n-r)! ^ (p-2)로 바꿈 
		long bottom	= pow(fac[R],P-2) * pow(fac[N-R],P-2) % P;
		
		return fac[N] * bottom % P;
		
	}
	
	// 분할 정복 a의 b승
	public static long pow(long a, long b) {
		if(b == 1) {
			return a;
		}
		long tmp = pow(a, b/2);
		if(b%2 == 1) return tmp*tmp%P*a%P;
		return tmp*tmp%P;
	}

}