[백준 11401번 C/C++] 이항 계수 3

 

[백준 11401번 C/C++] 이항 계수 3

 

https://www.acmicpc.net/problem/11401

 

---

 

 

해결전략

 

분할 정복을 이용한 거듭제곱
모듈로 곱셈 역원
페르마의 소정리

 

사실상 수학문제다. 모듈로 곱셈 역원과 페르마의 소정리를 찾아본 후 풀었다.

 

---

 

 

정답코드

 

#include <iostream> 
using namespace std;

const int MOD = 1000000007; 
long long n, k; 
long long answer; 

// 팩토리얼 계산 함수 (start부터 end까지의 곱을 계산)
long long fact(long long start, long long end) 
{
    long long ret = 1;  // 반환 값 초기화
    
    for (int i = start; i <= end; i++) {
        ret = ret * i % MOD;  // i를 곱한 후 MOD로 나머지 연산
    }
    
    return ret;
}

// 거듭제곱 계산 함수 (a^b % MOD 계산)
long long power(int a, int b) 
{
    if (b == 1) return a % MOD;  // 기본 경우: a^1 % MOD 반환
    
    long long half = power(a, b / 2);  // a^(b/2) 재귀 호출
    
    if (b % 2 == 1) { // b가 홀수인 경우
        return half * half % MOD * a % MOD;  // (a^(b/2))^2 * a % MOD
    } 
    else { // b가 짝수인 경우
        return half * half % MOD; 			// (a^(b/2))^2 % MOD
    }
}

int main() {
    cin >> n >> k;  // 사용자로부터 n과 k 입력 받음

    // 이항 계수 계산: (n-k+1부터 n까지의 팩토리얼) * (k!의 역원) % MOD
    answer = fact(n - k + 1, n) * power(fact(1, k), MOD - 2) % MOD;

    cout << answer;
    return 0;
}

 

---