BOJ) 11401. 이항 계수 3

(문제)

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

입력) 첫째 줄에 N과 K가 주어짐 $(1\leq N\leq 4000000, 0\leq K\leq N)$

출력) $N\choose K$를 1,000,000,007로 나눈 나머지를 출력한다.

조건) 시간 제한 1초, 메모리 제한 256MB


(풀이)

이항 계수를 알아내는 프로그램을 작성할 때, 우리는 어떠한 접근 방법이 있을까?
먼저, 가장 간단하게 생각할 수 있는 것은 이항 계수의 식을 이용하여 구하는 방식이다.

$$\binom{N}{K} = \begin{cases} n!/(k!(n-k)!) & 0\leq K \leq N \\ 0 & K < 0 \\ 0 & K > N \end{cases}$$

이 식은 파스칼의 법칙에 따라 다음과 같은 점화식으로 재정의할 수 있다.
$$\binom{N}{K} = \binom{N-1}{K-1} + \binom{N-1}{K}$$

따라서, N과 K가 작은 경우 메모이제이션 기법을 통해 다음과 같은 코드가 가능하다:

#include <stdio.h>
long long dy[10][10];
 
long long d(int a, int b){
    if(a<0 || b<0) return 0;
    if(dy[a][b]!=-1) return dy[a][b];
    if(a==b) return dy[a][b] = 1;
    if(b==1) return dy[a][b] = a;
    return dy[a][b] = (d(a-1,b-1) + d(a-1,b));
 
}
 
int main(){
    int N, K; scanf("%d%d",&N,&K);
    for(int i=0; i<=N; i++){
        for(int j=0; j<=K; j++){
            dy[i][j] = -1;
        }
    }
    printf("%lld",d(N,K));
}
 

하지만 이 방법에는 큰 단점이 있는데, N과 K가 급격히 커질 경우 실행 시간이 커진다는 점에 있다.

따라서, 본 문제에 접근하기 위해서는 1,000,000,007로 나눈 나머지를 출력한다는 점을 이용하면 쉽게 접근할 수 있다.

이 부분을 위해 먼저 이산수학에서 배우는 페르마의 소정리 내용을 되짚고 가자.

(페르마의 소정리)

먼저 p가 소수이고, a가 정수이며 p와 a가 서로소라 하자. 그럴 경우, a가 0 아닐 경우 다음과 같은 식이 성립한다.

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

이는 다음과 같이 증명할 수 있다:

(1) a와 서로소인 소수 p에 대해 $\{ a, 2a, 3a, ..., (p-1)a \}$는 p로 나누었을 때의 나머지가 모두 다르다.

(2) 또한 a와 p는 서로소이므로 $ia$는 p의 배수가 아니다.

(3) 집합 $A = \{x|x = ia, i \in \{1, ..., p-1\} \}$과 $B = \{1,2, ..., p-1\}$를 보자. (1)에 의해 $|A| = |B|$이므로, 다음과 같은 식을 유도할 수 있다.
$$a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times \cdots \times (p-1)  \text{(mod p)}$$
이때, 양변을 $(p-1)!$로 나누면,
$$a^{p-1} \equiv 1 \text{(mod p)}$$ 를 얻는다.

그렇다면 이 페르마의 소정리 내용을 어떻게 이용할 수 있을까?

modular p에 대하여 $1/(k! \times (n-k)!)$를 modular p에 대한 $k! * (n-k)!$의 역원을 구해주는 것으로 이용할 수 있다.

즉 $k! * (n-k)!$의 역원을 modular p에 대해 구해준 후, 이를 n!에 곱해주면 답을 계산해줄 수 있는 것이다.

그렇다는 것은 다음과 같은 수식을 유도할 수 있게 해준다:

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

이 때,  a가 $k! * (n-k)!$라면? 당연히 $a^{p-2}$가 $a$의 역원이 된다. 즉

$(k! \times (n-k)!)^{p-2} \times n! \equiv n!/(k!(n-k)!) \text{(mod p)}$를 만족하게 되는 것이다.

이 때, p-2의 제곱을 구하는 것은 divide and conquer를 이용해주면 가능하다.

#include <stdio.h>
#define mod 1000000007LL
typedef long long ll;
 
ll fac[4000001], inv[4000001];
 
ll power(ll x, int p){
 ll temp = 1;
 while(p>0){
  if(p%2) temp = (temp * x) % mod;
  x = (x * x) % mod;
  p/=2;
 }
 return temp;
}
 
int main() {
 int N, K; scanf("%d%d",&N,&K);
 fac[0] = 1;
 for(int i=1; i<=N; i++)
  fac[i] = (fac[i-1] * i) % mod;
 printf("%lld", (power((fac[K]*fac[N-K])%mod,mod-2)*fac[N])%mod);
}