[C++] 11402번 이항 계수 4 - 수학, 다이나믹 프로그래밍, 정수론, 조합론, 뤼카 정리

1. 문제

• 자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오.

<입력>

• - 1 -   \(N, K, M(1 \leq N \leq 10^{18}, 0 \leq K \leq N, 2 \leq M \leq 2,000, M is prime)\)

<출력>

• \(_{n}C_{k}\)를 \(M\)으로 나눈 나머지를 출력한다.

2. 재정의

• X

3. 해결 방법

• 뤼카의 정리를 이용하면 간단하게 풀 수 있다.

4. 실수한 점, 개선할 점

• binomial을 사용할 때 dp를 사용하지 않고 Euler's little theorem을 사용하면 0ms로 풀 수 있다.

 

<코드>

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

const int MAX_MOD = 2001;

// nCk 와 mod
ll N, K, M;

// 이항식
int binomial[MAX_MOD][MAX_MOD];

void input() {
    cin >> N >> K >> M;
    
    for(int i=0; i<M; i++) {
        binomial[i][0] = 1;
        for(int j=1; j<=i; j++)
            binomial[i][j] = (binomial[i-1][j-1] + binomial[i-1][j]) % M;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    int ret = 1;
    while(N || K) {
        ret = (ret * binomial[N%M][K%M]) % M;
        N /= M, K /= M;
    }
    
    cout << ret;
    
    return 0;
}

 

<뤼카의 정리>

https://bowbowbow.tistory.com/2

Lucas Theorem : 뤼카의 정리

 

<문제 바로가기>

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

11402번: 이항 계수 4

 

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