SWEA. 5607. 조합(페르마의 소정리)

 

  그냥 풀면 터진다. 조합의 경우의 수가 매우 커지기 때문이다. 결과값은 모듈러 연산 후의 값을 출력하고, 연산하는 모듈러 값은 소수이므로 페르마의 소정리를 이용해서 구현하면 된다.

    모듈러 연산을 제곱형식으로 바꿀 수 있다는게 아이디어의 핵심이다. 이후의 거듭제곱 함수는 분할정복 방식으로 바꿔서 복잡도를 logn으로 낮춰주는것도 중요하다. 이어서 뤼카의 정리도 알아두면 좋다.

페르마의 소정리 - 나무위키

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGKdbqczEDFAUo&

SW Expert Academy

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

public class SWEA5607조합 {

	static int n, r;
	static final long MOD = 1234567891;
	static long up,down;
	static long factorial[];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		// 팩토리얼 초기화
		factorial = new long[1000001];
		factorial[0] = 1;
		for(int i=1; i<1000001; i++) {
			factorial[i] = (factorial[i-1]*i)%MOD;
		}
		// testcase 선언
		int TC = Integer.parseInt(br.readLine());
		for(int i=1; i<=TC; i++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());
			// 계산식
			up = factorial[n]%MOD;
			down = ((factorial[r]%MOD)*(factorial[n-r]%MOD))%MOD;
			// 결과값
			sb.append("#"+i+ " " +((up*pow(down,MOD-2))%MOD) + "\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static long pow(long base, long power) {
		if(power==0) return 1;
		long half = pow(base,power/2);
		
		if(power%2==0) {
			return ((half % MOD)*(half % MOD)) % MOD;
		}else {
			return ((((half % MOD)*(half % MOD)) % MOD)*base) % MOD;
		}
	}

}