[백준 11401] 이항 계수 3 [C]

백준 - 11401

---

풀이

MOD가 소수이기 때문에, A = N! - (N-K)!와 B = K!를 MOD로 나누며 구하고,

Fermat’s little theorem를 이용해 ( A* B^(MOD-2) )%MOD를 구하면 된다.

---

소스코드

#include <stdio.h>
const int MOD = 1e9+7;
int main(){
    long long N, K, A = 1, B = 1;
    scanf("%d %d", &N, &K);
    for (int i = N; i > N-K; i--)
        A = A*i %MOD;
    for (int i = K; i >= 2; i--)
        B = B*i %MOD;
	
    N = 1, K = MOD-2;
    while (K){
        if (K & 1) N = N*B %MOD;
        K >>= 1;
        B = B*B %MOD;
    }
    printf("%d", A*N %MOD);
}

---

출처 및 참고자료

11401번: 이항 계수 3

[백준 13172] Σ [C]