(c++) BOJ 11401번: 이항 계수 3

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

 

---

 

 

 

문제 개요

 

 

코드 작성이 어렵다기보다 페르마의 소정리를 이용하여 큰 수에 대한 거듭제곱을 수행하면 된다.

 

페르마의 소정리를 이 문제에 적용시키는 것이 관건이다.

 

먼저 이항 정리의 식을 알고 가야 한다.

 

 $$ \binom{N}{K} = \frac{n!}{(N-K)!K!} $$

 

그리고 페르마의 소정리를 간단하게 보면

 

$$ a^{p} \equiv a (mod \; p) $$

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

 

이 수식을 이항 정리에 적용해보면

 

$$ \frac{n!}{(N-K)!K!} = n! \times ((N-K)!K!)^{-1} $$

$$ ((N-K)!K!)\ast ((N-K)!K!)^{-2} \equiv  1(mod\; p) $$

$$ ((N-K)!K!)^{-2} \equiv  ((N-K)!K!)(mod\; p) $$

 

그래서 p가 1,000,000,007이라고 했을 때

 

$$ \binom{N}{K} \equiv  N! \ast ((N-K)!K!)^{p-2}  $$

 

이것이 성립하게 된다.

 

p-2번의 거듭제곱을 분할 정복으로 처리하면 된다.

 

 

 

코드

 

 

#include <bits/stdc++.h>
#define DIV 1000000007
using namespace std;

int n, k;
long long f_nk;
// 팩토리얼
long long fac(long long x) {
    if (x == 1 || x == 0) return 1;
    return (fac(x - 1) % DIV) * x % DIV ;
}
// 제곱
long long mult(long long m) {
    m %= DIV;
    return m * m % DIV;
}
// 분할 정복
long long prime(long long p) {
    if (p == 1) return f_nk;
    if (p % 2 > 0) return prime(p - 1) * f_nk % DIV;
    return mult(prime(p / 2)) % DIV;
}

int main(void) {
    cin >> n >> k;
    f_nk = fac(n-k) * fac(k) % DIV;
    long long fib_n = fac(n) % DIV;
    cout << (fib_n * prime(DIV-2) % DIV);
}