[C++] 13977번 이항 계수와 쿼리 - 수학, 정수론, 조합론, 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 페르마의 소정리

1. 문제

• M개의 자연수 N과 정수 K가 주어졌을 때 이항 계수 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 구하는 프로그램을 작성하시오

<입력>

• - 1 -   \(M(1 \leq M \leq 100,000)\)
• - M개의 줄 -   \(N, K(1 \leq N \leq 4,000,000, 0 \leq K \leq N)\)

 

<출력>

• M개의 줄에 \(_{n}C_{k}\)를 \(1,000,000,007\)로 나눈 나머지를 출력한다.

2. 재정의

• X

3. 해결 방법

• factorial값을 모두 저정한 다음 페르마의 소정리를 이용해 간단하게 풀면 된다.

4. 실수한 점, 개선할 점

• 항상 나오지만 자료형 범위 조심하자
• 분할 정복 사용할 때 재귀 함수를 사용하지 않고 반복문을 이용해하는 방법도 있었다. 이렇게 한 코드가 있어서 아래에 참고하였다.
• 또 fastio로 매크로를 사용해서 위로 올리니까 코드가 보기 깔끔해진 것 같다.

 

<코드>

#include <iostream>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

const int MAX_N = 4000001;
const int mod = 1000000007;

// <문제>
// 쿼리의 개수 M, NCK
ll M, N, K;

// 팩토리얼
int fact[MAX_N];

ll Pow(ll a, int b) {
    ll ret = 1;
    while(b) {
        if(b & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

void input() {
    cin >> M;
    
    fact[0] = 1;
    for(int i=1; i<MAX_N; i++)
        fact[i] = 1ll*fact[i-1] * i % mod;
}

int main() {
    fastio;
    
    input();
    
    for(int i=0; i<M; i++) {
        cin >> N >> K;
        cout << fact[N] * Pow(1ll*fact[K] * fact[N-K] % mod, mod-2) % mod << '\n';
    }
    
    return 0;
}

 

<참고한 코드>

https://www.acmicpc.net/board/view/86891

글 읽기 - const 키워드 쓴다고 2배나 속도가 차이가 나나요?

 

<문제 바로가기>

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

13977번: 이항 계수와 쿼리

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.