PS/Baekjoon Online Judge

[백준 16134] 조합 (Combination)[C]

kimyoungrok 2021. 8. 28. 02:46

백준 - 16134


풀이

"백준 11401, 이항 계수 3"보다 N의 범위가 작은 문제이다.


소스코드

#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);
}

출처 및 참고자료

 

16134번: 조합 (Combination)

\(\begin{pmatrix}N\\R\end{pmatrix}\)의 값을 1,000,000,007로 나눈 나머지를 출력하자! (단, 1,000,000,007은 소수이다)

www.acmicpc.net

 

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

풀이 A = N! - (N-K)!와 B = K!를 MOD로 나누며 구하고, 페르마의 소정리를 이용해 ( A* B^(MOD-2) )%MOD를 구하면 된다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long N, K, A = 1, B = 1;..

kyr-db.tistory.com