이항 계수 3 - 11401

//이항 계수 3 - 11401
 
#include <iostream>
using namespace std;
 
int N, K;
long long ans;
const long long MOD = 1000000007;
 
long long revM(int a)
{
    long long old_r, r, temp_r;
    long long old_s, s, temp_s;
    long long old_t, t, temp_t;
    long long q;
    old_r = a, r = MOD;
    old_s = 1, s = 0;
    old_t = 0, t = 1;
 
    while(r)
    {
        q = old_r/r;
        temp_r = r;
        r = old_r - r*q;
        old_r = temp_r;
 
        temp_s = s;
        s = old_s - s*q;
        old_s = temp_s;
 
        temp_t = t;
        t = old_t - t*q;
        old_t = temp_t;
    }
    while(old_s < 0)
        old_s += MOD;
    return old_s;
}
 
int main()
{
    cin >> N >> K;
    ans = 1;
 
    for(long long i = 1; i<=K; ++i)
        ans *= (N-i+1), ans %= MOD, ans *= revM(i), ans %= MOD;
    cout << ans;
}

 

 

 

 

 

 

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

11401번: 이항 계수 3

 

 

 

 

 

 

이항 계수 3

이항계수 nCk 는

n*(n-1)*(n-2)*....(n-k+2)*(n-k+1)

을

1*2*3*4*.....*(k-1)*k로 나누어주면 됩니다.

하지만 그 수가 팩토리얼로 증가하기 때문에 조금만 숫자가 커져도 오버플로가 생기기 때문에

곱셈과 나눗셈의 순서를 적절히 조합해 오버플로를 방지해야 합니다.

따라서 중간중간 연산과정에 계속 modular 연산을 해야하는데 문제는 나눗셈에 대한 modular연산은 분배법칙이 성립하지 않기 때문에 a/b 를 a/a' (a'는 a의 곱셈에 대한 역원입니다.)

바꾸어 주어야 합니다. 이때 a의 modular M 연산계에 대한 곱셉의 역원을 구하기 위해 특정 조건에서 몇가지 방법을 사용할 수 있습니다.

M의 값이 소수라면 페르마소정리를 이용할 수 있고, 소수가 아니더라도 a와 M이 서로소라면 확장 유클리드 호제법을 이용할 수 있습니다. 자세한 내용은 밑에 주소를 참조해 주세요!

https://onedaycoding.tistory.com/137

Modular 연산에서 나눗셈

저는 확장 유클리드 알고리즘을 이용했습니다!