이항 계수 3 C++ - 백준 11401

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

배경 지식 1. 확장 유클리드 알고리즘

배경 지식 2. 모듈러 역원

배경 지식 3. 페르마의 소정리

오늘은 정말 많은 것을 배운 것 같아서 뿌듯하다.

문제 접근

문제 내용은 간단하다 이항 계수 $n\choose k$를 구하면 된다.

하지만 n의 범위가 $4e6$이기 때문에 조합의 성질인

$n\choose k$$=$$n-1\choose k$$+$$n-1\choose k-1$를 사용하지 못한다.

그렇다면 실제로 팩토리얼을 구현하는 방법 밖에 없다.

문제 풀이 1 - 페르마의 소정리

팩토리얼을 구현할 때 문제되는 것이 나눗셈 모듈러 연산 때문이다.

나눗셈 모듈러 연산은 모듈러 곱셈 역원을 사용해야 한다.

보통 PS에서 큰 수를 다룰 때 오버플로우를 방지하기 위해

소수로 모듈러 연산 처리를 하는 과정이 있는데

이 점을 이용하여 페르마의 소정리를 사용한다.

페르마의 소정리의 의하여 소수 $P$에 대해

$a^{P-2}\equiv a^{-1}\;mod\;P$이기 때문에

결과에 곱셈 역원을 곱해주면 된다.

근데 주의할 점은 $P$가 10억이기 때문에 분할 정복 제곱을 사용해야 한다는 점이다.

문제 풀이 2 - 확장 유클리드 알고리즘

마찬가지로 곱셈 역원을 구해주기 위해 확장 유클리드 알고리즘을

사용하면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define MOD 1000000007ll
typedef long long ll;
using namespace std;

// using Fermat Theorem or Extended Euclidean Algorithm

ll p(ll a, int n){
    if(n==0) return 1;
    if(n==1) return a;
    ll b=p(a,n/2); b*=b; b%=MOD;
    if(n%2) return (b*a)%MOD;
    return b;
}

pair<ll,pair<ll,ll>> xGCD(ll a, ll b){
    if(b==0) return {a,{1,0}};
    pair<ll,pair<ll,ll>> ret=xGCD(b,a%b);
    ll g,x,y;
    g=ret.first;
    tie(x,y)=ret.second;
    return {g,{y,x-a/b*y}};
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n,k,t=1,b=1;
    cin >> n >> k;
    for(int i=0;i<k;i++){
        t*=n--;
        t%=MOD;
        b*=(ll)(i+1);
        b%=MOD;
    }
    // cout << (t*p(b,MOD-2))%MOD;
    ll inv=xGCD(MOD,b).second.second;
    inv+=MOD*(-inv/MOD+1);
    inv%=MOD;
    cout << (t*inv)%MOD;
    return 0;
}