Baekjoon11401: 이항 계수3

풀이1 이항계수의 다항식성질

이항계수의 다항식의 성질을 생각할 수 있지만 반복문을 사용하기 때문에 시간초과가 발생한다.

4백만 크기의 n을 입력하면 시간초과는 뻔하기 때문에 백준에 입력하지는 않았다.

<x+1의 n승 다항식 계수 구하기>
현재 배열의 값들을 오른쪽으로 한칸씩 옮기는데 오른쪽 끝부터 오른쪽으로 한 칸씩 옮긴다.
옮기면서  원래 그 자리에 있던 수와 더한다.

이를 마치면 (n k) 줄에 해당하는 식이 완성되어있고 이 배열의 k번째 index의 값을 출력하면 된다.

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N+1];
		arr[0]=1;
		for(int i=0;i<N;i++) {
			for(int j=i;j>=0;j--) {
				arr[j+1]=(arr[j+1]+arr[j])%1000000007;
			}
		}
		System.out.println(arr[sc.nextInt()]);
}}

풀이2 배열을 이용한 분할정복

결국 2배씩 앞당겨서 찾는 방법을 생각해야했는데, 위 다항식을 분할정복을 통해 구현할 수 있다.

예를 들면 0번째줄부터 4번째 줄을 나타내면 다음과 같이 (x+1)^n의 다항식 계수로 표현할 수 있을 것이다.

1 = (x+1)의 0승

1  1 = x+1

1 2 1 = x^2 + 2x + 1 = (x+1)^2

1 3 3 1 = (x+1)^3

이를 통해 (n k)의 결과값은 (x+1)^n의 k번째 항의 계수임을 알 수 있고

규칙성을 이용해 n을 절반으로 쪼개가며 다항식의 곱으로 표현할 수 있다.

(x+1)^n = (x+1)^n/2 * (x+1)^n/2

메소드

(x^2+2x+1) (x+1)의 결과를 어떻게 표현할 수 있을까?

배열로 나타내면 {1, 2, 1, 0}, {1, 1, 0, 0} 이다.

{1, 2, 1, 0}, {1, 1, 0, 0}: 각 index는 x가 몇번 곱해져있는지 알려준다. 오른쪽부터 계산하면 → {0, 0, 0, 1}

{1, 2, 1, 0}, {1, 1, 0, 0}: index[0]을 곱하면 자리는 변하지 않는다  → {0, 0, 1, 1}

{1, 2, 1, 0}, {1, 1, 0, 0}: index[1]을 곱하면 자리는 +1만큼 변한다  → {0, 0, 3, 1}

{1, 2, 1, 0}, {1, 1, 0, 0}: index[0]을 곱하면 자리는 변하지 않는다  → {0, 2, 3, 1}

다항식의 연산과 분할정복을 합해봤지만 시간초과였다

import java.util.*;
public class Main {
	static int N;
	static long[] arr;
	static long[] pascal(int N) {
		if(N==0 || N==1) {
			return arr;
		}
		long[] before = pascal(N/2);
		long[] answer = cal(before,N/2+1,before,N/2+1);
		if(N%2==0) {
			return answer;
		}else {
			return cal(answer,N-1,arr,2);
		}
	}
	static long[] cal(long[] A, int lenA,long[] B, int lenB) {
		long[] C = new long[N+1];
		for(int i=0;i<lenA;i++) {
			for(int j=0;j<lenB;j++) {
				long num = A[i]*B[j]%1000000007;
				C[i+j]+=num;
			}
		}
		return C;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new long[N+1];
		arr[0]=1;
		arr[1]=1;
		System.out.println(pascal(N)[sc.nextInt()]);
}}

풀이 3 페르마 소정리를 이용한 분할정복

성질을 이용해서 4000000 사백만의 n에 도달하는 것은 어렵다고 결론지었다.

결국 자체식인 (n k) = n!/k!(n-k)! 을 사용해야했다.

나눗셈이 들어간 식에서 모듈러 연산을 사용할 수 없기 때문에 모듈러 연산을 사용하기 위해 등식을 이용해 식을 변경한다.

(n k) = B/A = B*A^-1 = n!/k!(n-k)! → A = k!(n-k)! → A^-1 = 1 / k!(n-k)! 의 식으로 나타낼 수 있고 페르마의 소정리를 적용한다.

<페르마의 소정리: p가 모듈러>
A^(p-1) ≡ 1
A^(p-2) ≡ A^-1 

이에 위의 식은 (n k) = B/A =  n!/k!(n-k)! → n! * {k!(n-k!)}^(1000000007-2) 가 된다.

메소드1

각각의 팩토리얼을 계산하는 메소드를 만든다.

예시) n! → n번 곱하면서 모듈러 연산진행

메소드2

분할정복으로 지수승을 구하는 메소드를 만든다.

import java.util.*;
public class Main {
	static long MOD = 1000000007;
	static long Factorial(int n) {
		long sum=1;
		for(int i=1; i<=n; i++) {
			sum=(sum*i)%MOD;
		}
		return sum;
	}
	static long power(long a, long b) {
		if(b==1) {
			return a;
		}
		long before = power(a,b/2)%MOD;
		long now = before*before%MOD;
		if(b%2==0) {
			return now;
		}else {
			return now*a%MOD;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		long A = Factorial(N),B = Factorial(K),C = Factorial(N-K);
		long D = B*C%MOD;
		System.out.println(A*power(D,MOD-2)%MOD);
}}