[SWEA 5607] [Professional] 조합 (JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGKdbqczEDFAUo

SW Expert Academy

1. 주의할 점

- 페르마의 소정리를 이용해서 풀어야 한다.

- Pow연산시 분할정복을 이용해야 시간초과가 발생하지 않는다

 

2. 구현

- nCr = (n)!/{(n-r)!*(r!)}이 성립하며, 각 숫자에 대한 팩토리얼%MOD의 값은 미리 구해놓는다 -> 시간절약

- nCr % MOD = up/down의 식으로 바꾼다.

up = n!%MOD, down = {(n-r)!%MOD *(r!)%MOD}%MOD 이 성립한다.

(up/down) %MOD = [up*{down^(MOD-2)}%MOD]%MOD 가 성립힌다 (페르마의 소정리에 의해)

- down^(MOD-2)를 계산하기 위해 Pow함수를 실행한다.

- Pow함수에서는 밑과 지수를 입력받는다(분할정복 적용)

만약 지수가 0이면 1을 return

지수가 1이면 밑을 return

지수가 1보다 크고 짝수면 {Pow(밑,지수/2)*Pow(밑,지수/2)}%MOD 를 return -> 분할정복

지수가 1보다 크고 홀수면 {Pow(밑,지수-1)*밑}%MOD 를 return

 

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

public class Solution_d3_5607_조합 {
	static int n,r;
	static final long MOD = 1234567891;
	static long fact[];
	public static long pow(long a, long remain) {
		if(remain==0) return 1;
		else if(remain==1) return a;
		if(remain%2==0) {
			long temp = pow(a,remain/2);
			return (temp*temp)%MOD;
		}
		long temp = pow(a,remain-1)%MOD;
		return (temp*a)%MOD;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine());
		fact = new long[1000001];
		fact[0]=1;
		for(int i=1;i<1000001;i++) {
			fact[i]=fact[i-1]*i;
			fact[i]%=MOD;
		}
		for(int t=1;t<=test;t++) {
			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			n = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());
			
			long up=1,down=1;
			up = fact[n];
			down = (fact[n-r]*fact[r])%MOD;
			down = pow(down,MOD-2);
			System.out.println("#"+t+" "+(up*down)%MOD);
		}
	}
}