[Java+Python]11401번, 이항 계수 3

목차

 

분할 정복 단계

[Java+Python]2630번, 색종이 만들기

[Java+Python]1992번, 쿼드 트리

[Java+Python]1780번, 종이의 개수

[Java+Python]1629번, 곱셈

[Java+Python]2740번, 행렬 곱셈

[Java+Python]10830번, 행렬 제곱

[Java+Python]11444번, 피보나치 수 6

[Java+Python]6549번, 히스토그램에서 가장 큰 직사각형

 

문제

 

자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $\binom{N}{K}$를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 $N$과 $K$가 주어진다. (1 ≤ $N$ ≤ 4,000,000, 0 ≤ $K$ ≤ $N$)

 

출력

 

$\binom{N}{K}$를 1,000,000,007로 나눈 나머지를 출력한다.

 

풀이

 

이 문제를 풀기 위해선 사전지식이 두 개 필요하다.

 

하나는 이항 계수 $\binom{N}{K}$의 계산 방법인데, 이는 아래와 같다.

 

$$\frac{n!}{k!(n - k)!}$$

 

두 번째는 페르마의 소정리인데, $a$가 정수, $p$가 소수일 때 수식으로 나타내면 아래와 같으며

 

$$a^{p - 1} \equiv 1(\mod p)$$

 

위 식은 $a^{p-1}$을 $p$로 나누면 나머지가 1이 된다는 것을 의미한다. 여기서 양 변을 $a$로 나눠주면 다음과 같은데,

 

$$a^{p - 2} \equiv \frac{1}{a}(\mod p)$$

 

즉, 위 조건을 만족하는 수의 경우 $a^{p-2}$를 p로 나누면 자기 자신의 역원($a^{-1}$)이 된다는 뜻이며,

 

이를 이용하면 빠르게 $r! \times (n-r)!$의 역원을 구할 수 있다.

 

나머지는 직전 문제에서 풀었던 고속 거듭제곱을 이용하면 된다. 알고리즘의 순서는 다음과 같다.

 

1. 입력으로 주어지는 n과 k를 받아 저장하고, $n!$까지의 값을 factorial 배열(리스트)에 미리 저장해 둔다.
2. 문제의 조건에서 주어진 1000000007은 소수이므로 페르마의 소정리에 이용하기 위해 p에 저장한다.
3. $\frac{n!}{k!(n - k)!}$의 분모 $k!(n - k)!$를 빠르게 구하기 위해 $k!(n - k)!(\mod p)$를 denominator에 저장한다.
4. 이어서 $\frac{1}{k!(n - k)!}$을 $denominator^{p - 2}$로 치환한 뒤 고속 거듭제곱 함수 power를 호출한다.
   1. 지수가 1이 될 때까지 거듭제곱의 지수를 반으로 나누어 문제를 분할해 자기 자신을 아래와 같이 호출한다.
      long half = pow(base, exponent / 2);
      여기서 half는 int 범위를 넘어설 수 있기 때문에 long으로 선언해주어야 한다.
   2. 지수가 1이 된 경우 병합과정이 시작된다. 각 단계에서 지수가 짝수인 경우엔 $half^2 (\mod p)$ 를,
      지수가 홀수인 경우엔 $((half^2 (\mod p)) \times base) (\mod p)$ 를 계산한다.
5. 계산 결과인 $n! \times denominator^{p - 2}$를 출력한다.

 

Java

 

package BackJoon;

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

public class Prob11401 {

	static final long p = 1000000007;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		long[] factorial = new long[n + 1];
		factorial[0] = 1;
		factorial[1] = 1;

		for (int i = 2; i <= n; i++) {
			factorial[i] = (factorial[i - 1] * i) % p;
		}

		long denominator = (factorial[k] * factorial[n - k]) % p;

		System.out.println((factorial[n] * power(denominator, p - 2)) % p);

	}

	private static long power(long base, long exponent) {

		if (exponent == 1) {
			return base % p;
		}

		long half = power(base, exponent / 2);

		if (exponent % 2 == 0) {
			return (half * half) % p;
		} else {
			return (((half * half) % p) * base) % p;
		}
	}
}

 

Python

 

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
p = 1000000007

fac = [0] * (n + 1)
fac[0] = fac[1] = 1

for i in range(2, n + 1):
    fac[i] = (fac[i - 1] * i) % p

denominator = (fac[k] * fac[n - k]) % p


def power(base, exponent):
    if exponent == 1:
        return base % p

    half = power(base, exponent // 2)

    if exponent % 2 == 0:
        return (half**2) % p
    else:
        return (((half**2) % p) * base) % p


print((fac[n] * power(denominator, p - 2)) % p)

 

Performance