[Algorithm] 범위에 따른 이항계수 구하는 방법

이항 계수는 기본적으로 factorial 을 이용해서 계산하기 때문에 수가 클 경우 일반적인 방법으로 계산하기 쉽지 않습니다. 그래서 각 경우에 대해서 어떻게 구해야하는지 알아보도록 하겠습니다.

 

이항계수 1

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

11050번: 이항 계수 1

n 과 k 의 값이 10 이하의 수로 굉장히 작습니다. 그렇기 때문에 fac_list 에 factorial 값을 미리 계산해놓고 index 로 참조하여 이항계수를 빠르게 구할 수 있습니다.

#include <iostream>

using namespace std;

int fac_list[11];

int main(int argc, const char * argv[]) {
    
    fac_list[0] = 1;
    
    for (int i=1;i<11;i++){
        fac_list[i] = fac_list[i-1] * i;
    }
    
    int n,k;
    cin >> n >> k;
    
    cout << fac_list[n] / (fac_list[n-k]*fac_list[k]) << "\n";
    
    
    return 0;
}

 

 

이항계수 2

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

11051번: 이항 계수 2

파스칼삼각형에 의해 아래와 같은 점화식이 성립합니다.

// C[n][k] : n 개 중에 k 개를 순서없이 고르는 방법
C[n][k] = C[n-1][k-1] + C[n-1][k];

파스칼 삼각형

이를 통해 원하는 값까지 파스칼 삼각형을 구할 수 있습니다.

#include <iostream>

using namespace std;

int coe_list[1001][1001];
const int DIV = 10007;

int main(int argc, const char * argv[]) {
    
    int N,K;
    cin >> N >> K;
    
    for (int n=0;n<=N;n++){
        coe_list[n][0] = 1;
        coe_list[n][n] = 1;
        for (int k=1;k<n;k++){
            coe_list[n][k] = coe_list[n-1][k] + coe_list[n-1][k-1];
            coe_list[n][k] %= DIV;
        }
    }
    cout << coe_list[N][K] << "\n";
    return 0;
}

 

 

이항계수 4

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

11402번: 이항 계수 4

n 의 범위가 10^18 이기 때문에 파스칼 삼각형을 사용해서도 구할 수 없습니다. 하지만 M 의 나눈 나머지를 구하는 것이므로 이럴 경우, 뤼카의 정리 를 이용합니다.

뤼카의 정리

음이 아닌 정수 m,n 소수 p 에 대해서 다음과 같은 식이 성립합니다.

뤼카의 정리 공식

이 때 mi 와 ni 는 아래 식과 같이 m,n 을 p 진수로 표현했을 때의 계수가 됩니다.

뤼카의 정리 p진법 표현

 

증명은 위키피디아 를 참조하시면 됩니다.

#include <iostream>
#include <vector>
using namespace std;
using namespace std;
int main() {
    long long n,r,p;
    cin >> n >> r >> p;
    vector<vector<int>> d(p+1,vector<int>(p+1));
    for (int i=0; i<=p; i++) {
        d[i][0] = d[i][i] = 1;
        for (int j=1; j<=i-1; j++) {
            d[i][j] = d[i-1][j-1] + d[i-1][j];
            d[i][j] %= p;
        }
    }
    vector<int> a,b;
    while (n > 0 || r > 0) {
        a.push_back(n%p);
        b.push_back(r%p);
        n/=p;
        r/=p;
    }
    long long ans = 1;
    for (int i=0; i<a.size(); i++) {
        ans *= d[a[i]][b[i]];
        ans %= p;
    }
    cout << ans << '\n';
    return 0;
}

a 벡터와 b 벡터에 p 진수로 표현했을 때의 계수들을 저장하여 이를 통해 뤼카의 정리로 답을 구할 수 있습니다.