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

문제링크 : https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

const int MOD = 1000000007;

ll func(ll a, ll b) //분할 거듭제곱
{
    ll tmp = 1;
    while(b)
    {
        if(b%2) tmp = tmp * a % MOD; //홀수
        a = a * a % MOD; //짝수
        b /= 2;
    }
    return tmp;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N, K;
    cin >> N >> K;
    ll result = 0, NN = 1, KK = 1;

    for(int i=N; i>=N-K+1; i--) //분자부분
    {
        NN = NN * i % MOD;
    }

    for(int i=1; i<=K; i++) //분모부분
    {
        KK = KK * i % MOD;
    }
    
    result = (NN * func(KK, MOD-2)) % MOD; // a * b^(MOD-2) 
    cout << result % MOD;

    return 0;
}

최근 페르마의 소정리와 분할 정복을 이용한 거듭제곱을 풀다보니 같이 눈에 들어온 문제다.

 

먼저 이항계수(N, K)를 식으로 나타내고, 이를 정리하면 다음과 같은 식을 얻을 수 있다.

기본식 : N! / K!(N-K)!

N = 5, K = 3가정
5*4*3*2*1 / 3*2*1 * 2*1 = 5*4*3/3*2*1 

얻은 식 : N * N-1 * N-2 * .... N-K+1 / K!

이를 정리하면 다음과 같은 식을 얻을 수 있다.

 

A를 분자, B를 분모로 두고 페르마의 소정리를 이용하면 다음과 같은 식또한 얻을 수 있다.

A * B^(MOD-2)

 

따라서 반복문을 통해 분자와 분모를 곱해서 구해주고, 이를 페르마의 소정리를 이용한 식에 대입하여 또 이를 분할 정복을 이용한 거듭제곱을 이용해서 풀면 된다.

 

참고 문제링크 : https://blob-thinking.tistory.com/243

[백준 13172번] Σ (C++)