[BOJ11401] 이항계수3 & 페르마의 소정리

문제설명

문제 자체는 간단하다. 자연수 N과 정수 K (1<=N<=4000000, 0<=K<=N)이 주어질 때, 이항 계수 NCK 를 1,000,000,007로 나눈 나머지를 출력하는 문제이다.

접근법

nCr은 n!/(n-r)!r! 으로 정의되며, 조합 공식으로 알려져 있다.

n개의 원소를 가지는 집합에서 r개의 원소를 고르는 조합의 가지 수를 이항계수라한다.

일반적으로 이항계수 문제를 풀 때는 nCr = n-1Cr-1 + n-1Cr 공식을 이용하여, 메모이제이션하여 O(n^2)에 해결할 수 있다.

하지만, 이 문제는 N의 범위가 매우 커서 O(N^2)의 시간복잡도로는 풀 수 없다.

이런 경우 위에서 언급한 조합 공식 nCr = n! / (n-r)!r!로 문제를 접근한다.

이 공식은 팩토리얼 연산자로 구성되어 있고, 우리가 아는 팩토리얼은 숫자가 조금만 커져도 결과값이 어마어마하게 커진다. 그래서 문제에서도 주어진 수를 이용하여 모듈러 연산을 통해 나머지를 출력하게 하였다.

여기서 중요한 문제가 발생하는데, 나누기 연산은 모듈러 연산의 특징이 적용되지 않는다.

즉, (a/b) % p != ((a%p)/(b%p))%p 이다.

그렇기 때문에, 나누기 연산이 들어간 식을 곱셈 연산으로 된 식으로 변형시키는 방법이 필요하고, 이때 필요한게 페르마의 소정리 이다.

페르마의 소정리

수식과 수식기호가 많이 들어가서, 간단하게 이미지 파일을 첨부한다.

코드 리뷰

풀이 역시 이미지 파일을 첨부한다.

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

public class BOJ11401_이항계수3 {
	static final int MOD = 1000000007;
	static long fn=1,fk=1,fnk=1; //필요한 팩토리얼 값이 아닌 애들은 저장을 안하여 메모리를 줄인다.
	static int n,k;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		dp();
		long parent = (fk*fnk)%MOD; //페르마의 소정리를 적용해야 하는 분모
		long ans = calc(parent,MOD-2)%MOD; //페르마의 소정리를 적용한 값
		System.out.println((fn*ans)%MOD);
	}
	static long calc(long n,int parent) { 
        //페르마의 소정리는 거듭제곱 형태이므로, 분할정복을 이용하여 시간 최적화
		if(parent==0) return 1;
		long tmp = calc(n,parent/2);
		long result = tmp*tmp%MOD;
		if(parent%2==0) return result;
		else return (result*n)%MOD;
	}
	static void dp() { //팩토리얼 연산
		long f = 1;
		for(int i=1; i<=n; i++) {
			f = (f*i)%MOD;
			if(i==n) fn = f; //필요한 팩토리얼 애들만 저장
			if(i==n-k) fnk = f;
			if(i==k) fk=f;
		}
	}
}