Q5_11401(이항 계수 3)

 

📌 문제

문제)
이항 계수 3 자연수 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로 나눈 나머지를 출력한다.
시간 제한 : 1초 메모리 제한 : 256 MB

📌 문제 분석❗️

가끔 이렇게 문제를 푸는 키워드를 알려줄 때가 있다. 페르마의 소정리를 일반인 입장에서 알리가 없을테니 구글링해서 페르마의 소정리가 무엇인지 안다면 문제를 푸는 핵심 키워드가 될 것이다.

 

❗️모듈러 연산

모듈러 연산(참조)

 

---

❗️이항계수가 뭐임?

이항계수는 다음과 같은 식을 만족한다.

k는 0보다 크고 n보다 작으므로 결국 n! / k!(n-k)!) %  K를 구하라는 소리이다.

 

---

❗️페르마의 소정리

모듈러 연산은 나눗셈에 대해서는 모듈러 연산 공식이 존재하지 않는다.

따라서 1/(k!(n-k)!) 같은 경우 페르마의 소정리를 통해 다른 식으로 치환해야 한다.

 

 

1. 페르마의 소정리는 다음과 같은 식을 만족한다.

여기서 a = k ! * ( n - k ) ! 이고, b = 1,000,000,007 이다

 

 

2. b는 1 이상의 자연수(혹은 소수)이다. 따라서 1 (mod b)는 무조건 1이다.
aᵇ⁻¹ = 1

 

3. 양변을 a로 나눠보자.
aᵇ⁻² = a⁻¹

 

 

4. a와 b를 대입해보자.

 

5. 해당 식을 원래 식에 대입하면 최종적으로 다음과 같은 식이 된다. 

 

6. 모듈러 합동 공식을 적용

최종적으로 식이 도출되었다.

※ 괄호 하나 빠짐 : * (k! * ....) -> * ((k! * ....)

 

---

❗️분할 정복

• 모듈러 합동 공식을 통해  분할 정복의 범위가 다음과 같이 세 덩이로 나눠진다.
  1. n! modb
  2. ((k! modb)¹⁰⁰⁰⁰⁰⁰⁰⁰⁷⁻⁵ )modb
  3. (((n-k)! modb)¹⁰⁰⁰⁰⁰⁰⁰⁰⁷⁻⁵ )modb

각각에 대해 분할 정복을 진행하고 마지막에 modb를 해주면 끝이다.

📌 진행

❗️전역 변수

private static long P = 1_000_000_007;

함수 파라매터를 줄이기 위해 나누는 값(P)는 전역 변수로 뺐다.

 

---

❗️팩토리얼 분할 정복 메서드 구현

private static long modularFactorial(int N) {
    long factorialValue = 1L;
 
    while (N > 1) {
        factorialValue = (factorialValue * N) % P;
        N--;
    }
 
    return factorialValue;
}

n!, k!, (n-k)! 에 대해 모듈 계산을 하기 위한 메서드이다.

N! mod P = N! mod P * (N-1)! mod P ..... 로 표현되므로 감소하는 반복문을 거쳐 모듈 계산을 해준다.

 

---

❗️제곱 수에 대한 분할 정복 메서드 구현

private static long binomial(long base, long exponent) {
    if (exponent == 0) return 1;
    long powerToValue = binomial(base, exponent / 2);
    long totalValue = (powerToValue * powerToValue) % P;
 
    if (exponent % 2 == 1) return (base * totalValue) % P;
    else return totalValue;
}

(k! modb)¹⁰⁰⁰⁰⁰⁰⁰⁰⁷⁻⁵ 와 (n-k)! modb)¹⁰⁰⁰⁰⁰⁰⁰⁰⁷⁻⁵는 제곱 수에 대한 분할 정복을 또 해줘야된다.

Q4_1629(곱셈 참조)

 

---

❗️최종 계산

// 분자 N! mod P
long frontValue = modularFactorial(N);
 
// 분모 (K! * (N - K)!) mod P
long fermatValue = modularFactorial(K) * modularFactorial(N - K) % P;
System.out.println(frontValue * binomial(fermatValue, P - 2) % P);

최종적으로 메인메서드에서 위와 같이 계산하여 출력한다.

📌 전체 코드

package level21_분할정복_.Q5_11401;
import java.io.IOException;
 
public class Main {
    private static long P = 1_000_000_007;
 
    public static void main(String[] args) throws IOException {
 
        // 식 : N!/(K!*(N-K)!) mod P
        int N = readInt();
        int K = readInt();
 
        // 분자 N! mod P
        long frontValue = modularFactorial(N);
 
        // 분모 (K! * (N - K)!) mod P
        long fermatValue = modularFactorial(K) * modularFactorial(N - K) % P;
        System.out.println(frontValue * binomial(fermatValue, P - 2) % P);
 
    }
 
    private static long modularFactorial(int N) {
        long factorialValue = 1L;
 
        while (N > 1) {
            factorialValue = (factorialValue * N) % P;
            N--;
        }
 
        return factorialValue;
    }
 
 
    private static long binomial(long base, long exponent) {
        if (exponent == 0) return 1;
        long powerToValue = binomial(base, exponent / 2);
        long totalValue = (powerToValue * powerToValue) % P;
 
        if (exponent % 2 == 1) return (base * totalValue) % P;
        else return totalValue;
    }
 
 
    private static int readInt() throws IOException {
        boolean isNegative = false;
        int value = 0;
        while (true) {
            int input = System.in.read();
            if (input == ' ' || input == '\n') {
                return (isNegative) ? -1 * value :
                        value;
            } else if (input == '-') isNegative = true;
            else value = value * 10 + (input - 48);
        }
 
    }
}

 

📌 참조

모듈러 연산(참조)

페르마의 소정리(참조)