이항계수3

시간 제한 : 1초 / 메모리 제한 : 256 MB

문제

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

입력

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

출력

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

1. 이항계수의 성질

$(a+b)^n$ 꼴의 다항식을 전개했을 때, $a^rb^{n-r}(0\le r \le n)$ 의 계수를 의미한다.

(1) $\begin{pmatrix}N \\ K\end{pmatrix} = {}_NC_K = \frac{N!}{K!(N-K)!}$

(2) $\begin{pmatrix}N \\ K\end{pmatrix} = \begin{pmatrix}N-1 \\ K-1\end{pmatrix} + \begin{pmatrix}N-1 \\ K\end{pmatrix}$

2. 풀이 생각

(2) 의 성질을 사용하여 동적계획법 계산하듯이 계산할 수 있으나, N,K가 최대 4백만 인것을 생각하면, $O(N^2)$ 의 연산이 1초 내에 불가능하다는 것을 알 수 있다.

그러나 (1)의 성질을 사용하려고 보니, 분자 분모에 나머지(modulus) 연산을 그냥 적용할 수가 없다. 이를 해결하기 위해서 페르마의 소정리 를 이용해야한다.

$p$ 가 소수이고 $a$가 $p$의 배수가 아니면, $a^{p-1} \equiv 1 \text{ (mod p)}$ 이다.

즉, (1) 의 분자를 A, 분모를 B라 하면, $AB^{-1}$ 을 구하는 것이 정답이 된다.(P=1,000,000,007)

$B^{P-1} \equiv 1 \text{ (mod P)}$

$B^{P-1} = B\cdot B^{P-2} \equiv 1 \text{ (mod P)}$

$B^{P-2} \equiv B^{-1} \text{ (mod P)}$

$AB^{-1} \equiv AB^{P-2} \text{ (mod P)} = (A$

제곱연산은 분할정복으로 $O(log(N))$, 팩토리얼 연산은 $O(N)$ 의 시간 복잡도 안에 계산할 수 있으므로, 1초(~1억번 연산) 안에 해결할 수 있다.

코드

#include <iostream>
#define P 1000000007
using namespace std;
typedef long long int ll;
ll N, K;
ll pow(ll a, ll b) {
  if (b == 0) return 1;
  if (b % 2 != 0) return (a * pow(a, b - 1)) % P;
  ll half = pow(a, b / 2) % P;
  return (half * half) % P;
}
int main() {
  cin >> N >> K;
  ll A = 1, B = 1;
  for (int i = 1; i <= N; i++) {
    A *= i;
    A %= P;
  }
  for (int i = 1; i <= K; i++) {
    B *= i;
    B %= P;
  }
  for (int i = 1; i <= N - K; i++) {
    B *= i;
    B %= P;
  }
  cout << ((A % P) * (pow(B, P - 2) % P)) % P;
  return 0;
}