모듈로 곱셈 역원_팩토리얼 계산( BOJ 13977 )

#include <stdio.h>
#include <utility>
#define NMAX 4000001
#define MOD 1000000007
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> PAIR;
 
int M, N, K;
lint ret;
lint fac[NMAX];
 
lint gcd(lint a, lint b) {
    if(a == 0) return b;
    else if(b == 0) return a;
    else return gcd(b, a%b);
}
 
// kx = 1 (mod MOD)
// >> ax + by = b(a/bx + y) + (a%b)x = 1
PAIR inv(lint a, lint b) {
    if(a == 0) return make_pair(0, 1);
    else if(b == 0) return make_pair(1, 0);
    else {
        PAIR prev = inv(b, a%b);
 
        lint x = ((prev.second%MOD)+MOD)%MOD;
        lint y = prev.first - (a/b)*x;
 
        return make_pair(x, y);
    }
}
 
int main() {
    // init
    fac[0] = 1;
    for(int i=1;i<NMAX;i++) fac[i] = (fac[i-1]*i)%MOD;
 
    // input
    scanf("%d", &M);
    while(M--) {
        scanf("%d %d", &N, &K);
 
        // nCk = n! / (k! * (n-k)!)
        ret = ((fac[N] * inv(fac[K], MOD).first)%MOD * inv(fac[N-K], MOD).first )%MOD;
 
        // print
        printf("%lld\n", ret);
    }
}

 

참고

https://koosaga.com/63

이항계수 (nCr) mod p 계산하기