백준 13977번 이항 계수와 쿼리 (boj/13977.c)

확장유클라디안 알고리즘으과 메모이제이션을 사용하는 문제입니다. 모든 팩토리얼에 대해 normal modular와 inverse modular를 계산한 뒤, 입력값에 따라 처리합니다.

시간복잡도는 N의 최대값을 N, 제수를 M이라 할 때 O(NlogM)입니다.

#include <stdio.h>
#include <math.h>
#define MOD_N   1000000007
#define MAX_N   4000000
typedef long long lint;
int mem[MAX_N+1] = { 0, };
int inv[MAX_N+1] = { 0, };
int EEA(int i, int m){
    int Q, Q1, Q2;
    int S, S1, S2;
    int T, T1, T2;
    int M;
    Q1=i; Q2=m;
    S1=T2=1; S2=T1=0;
    for(;;){
        Q=Q1/Q2; M=Q1%Q2;
        S=S1-S2*Q; T=T1-T2*Q;
        if(!M){ break; }
        Q1=Q2; Q2=M;
        S1=S2; S2=S;
        T1=T2; T2=T;
    }
    if(S2<0){ S2+=m; }
    return S2;
}
void init(int N){
    mem[0]=1; inv[0]=1;
    for(int i=1;i<=N;i++){
        mem[i] = (lint)mem[i-1]*i % MOD_N;
        inv[i] = EEA(mem[i], MOD_N); }
    return;
}
int main(void){
    int M, N, K;
    lint tmp;
    init(MAX_N);
    scanf("%d", &M);
    for(int i=0;i<M;i++){
        scanf("%d %d", &N, &K);
        tmp = (lint)mem[N] * inv[N-K] % MOD_N;
        tmp = tmp * inv[K] % MOD_N;
        printf("%d\n", (int)tmp);
    }
    return 0;
}