백준 16134번 조합 - C++ 풀이

---

 

1. nCr = n! / (n-r)!r! 의 정의대로 계산한다.
2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다.

 

1. nCr = n! / (n-r)!r! 의 정의대로 계산한다.

 조합 nCr의 정의대로 반복문을 통해 계산할 것이다.

 

2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다.

 (A*B) mod C = (A mod C) * (B mod C) mod C 임을 이용하여 곱셈을 계산하고, 나눗셈의 경우 1,000,000,007이 소수이므로 모듈러 곱셈 역원을 이용하여 계산한다. 모듈러 곱셈 역원은 분할정복을 이용한 거듭제곱을 사용해서 구하면 된다.

 

반응형

---

#include <iostream>

using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

ll power(int a, int n) {
    if (n == 0) return 1;
    
    ll half = power(a, n/2);
    if (n % 2 == 0) return half * half % MOD;
    else return (half * half % MOD) * a % MOD;
}

int moduloInverse(int n) {
    return power(n, MOD-2);
}

int combination(int n, int r) {
    ll ret = 1;
    
    for (int i=0; i<r; i++) {
        ret = ret * (n-i) % MOD;
    }
    
    for (int i=r; i>=1; i--) {
        ret = ret * moduloInverse(i) % MOD;
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N, R;
    cin >> N >> R;
    
    cout << combination(N, R);

    return 0;
}