[백준(Baekjoon)][자바(java)] 11401 : 이항 계수 3 / 분할 정복

 

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

11401번: 이항 계수 3

 

 

< 문제 풀이 >

 

*  이항 계수 ( nCk )

 

1.  일반적 재귀 호출  -- 팩토리얼 

 nCk = n! / ( k! (n-k)! )

public static int factorial( int n ) {
	int res = 1;	
	for( int i = n; i >= 2; i-- )
		res *= i;	// res = res * i % 1000000007;
	return res;
}

 

2.  동적계획법  메모이제이션

 nCk = (n-1)Ck + (n-1)C(k-1)

static int[][] cache; 	// initialize all values to -1

static int bino( int n, int r ) {
	if( n == 0 || r == 0 || n == r ) return 1;
	if( cache[n][r] != -1 )   
		return cache[n][r];
	return cache[n][r] = ( bino( n-1, r-1 ) + bino( n-1, r ) ); // % 1000000007;
}

 

( 1, 2 방법은 수가 커지면 시간초과 )

 

3.  분할정복  + 페르마의 소정리

 nCk  =  n! / ( k! (n-k)! )   % p
        =  n! * ( k! (n-k)! )^(-1)   % p    ( a = n!, b = k!*(n-k)! )
        =  a * b^(-1)   % p
        =  a * b^(-1) * 1   % p              ( b^(p-1) % p = 1 )
        =  a * b^(-1) * ( b^(p-1) % p )   % p
        =  a * ( b^(p-2) % p )   % p
        =  ( ( a % p ) ( b^( p-2 ) % p ) )   % p

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), k = sc.nextInt();
		sc.close();
		long p = 1000000007;
		
		long f[] = new long[n+1];	// 팩토리얼 ( factorial )
		f[0] = 1;
		f[1] = 1;
		for( int i = 2; i <= n; i++ )
			f[i] = ( f[i-1]*i ) % p;
		long a = f[n];						// a : n!
		long b = ( f[k] * f[n-k] ) % p;	// b : k!*(n-k)!
		
		long e = p-2; 		// 지수 ( exponent )
		long b_pow_e = 1;	// b의 e 제곱 ( pow )
		while( e > 0 ) {
			if( e % 2 == 1 ) 
				b_pow_e = ( b_pow_e * b ) % p;	// b_pow_e *= b;  b_pow_e %= p;
            b = ( b * b ) % p;
			e /= 2;
		}
        
		System.out.println( ( ( a % p ) * ( b_pow_e % p ) ) % p );
	}
}

( 코드 참고 : https://onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/ )