Baekjoon 11401 (이항계수 3)

Baekjoon 11401, 백준 11401 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <iostream>
#include <vector>
using namespace std;

long long int multiply_split(long long int a, long long int b, long long int c) {  // a^b = ? (mod c)
    if(b == 0) return 1;
    if(b%2 == 1) return ((a%c) * (multiply_split(a, b/2, c)) % c * (multiply_split(a, b/2, c) % c)) % c;
    else return ((multiply_split(a, b/2, c) % c) * (multiply_split(a, b/2, c) % c)) % c;
}

int main() {
    long long int N, K;
    cin >> N >> K;
    long long int DIVIDER = 1000000007;
    vector<long long int> index_factorial;
    index_factorial.push_back(1);  // 0! = 1
    long long int val = 1;

    for(long long int i = 1; i <= N; i++){
        val = (val * i) % DIVIDER;
        index_factorial.push_back(val);
    }
    long long int temp1 = (index_factorial[K] * index_factorial[N-K]) % DIVIDER;
    long long int temp2 = multiply_split(temp1, DIVIDER-2, DIVIDER) % DIVIDER;
    long long int temp3 = (index_factorial[N] * temp2) % DIVIDER;
    cout << temp3 << '\n';
}

“페르마의 소정리”를 이용하는 문제였다. (너무 오랜만이 아닌가..)
a^(p-1) = 1 (mod p) 이며, 따라서 a^(p-2) = a^(-1) (mod p) 의 아이디어를 사용한다.
거듭제곱은 분할정복으로 처리.
1부터 N까지의 팩토리얼 값들이 저장된 index를 아예 O(N)으로 만들고, 갖다 쓰는 것이 아이디어.