[Baekjoon,11401]이항 계수 3

해결

첫 접근

1. 이항 계수 정리
   처음 드는 생각은 아래와 같은 이항 계수의 정리를 이용하는 것이다.
   
   하지만 나머지 연산을 해야 하는데 분모가 있어 진행할 수 없다.

2. 이항 계수의 항등식
   다른 방법을 찾던 중 아래의 이항 계수의 항등식을 이용하는 것을 떠올렸다.
   
   하지만 이 방법은 4백만이라는 입력을 감당할 수 없다.

페르마의 소정리로 1번의 문제를 해결

페르마의 소정리는 다음과 같다. 증명은 생략하겠다.

이는 a는 p의 배수가 아니고 p는 소수일 때 a를 p-1 제곱 한 값을 p로 나눈 나머지가 1 이라는 것이다.

이를 이용하여 1번 내용의 분모를 분자로 변환할 수 있다. 즉, 나머지 연산이 있는 경우 분모의 값을 분자로 변환할 수 있다는 것이다. 분모의 값인 k!(n-k)!를 b라고 했을 때 페르마의 소정리를 이용하여 분자로 변환할 수 있는 것이다.

b^(p-1) ≡ 1 (mod P)
b*b^(p-2) ≡ 1 (mod P)
b^(p-2) ≡ b^(-1) (mod P)

즉, MOD 값이 100000007이니 여기서 2를 뺀 값 100000007-2 만큼 b를 제곱하면 나머지 연산이 해결된다.

구현

분할 정복을 이용하여 제곱을 빠르게 구하는 것을 볼 수 있다.

#include <iostream>
using namespace std;

const long long MOD=1000000007LL;
int N,K;

long long pow(long long a, long long b)
{
    if(b==0) return 1;
    if(b%2>0) 
        return (pow(a,b-1)*a)%MOD;
    long long mid=pow(a,b/2)%MOD;
    return (mid*mid)%MOD;
}

int main()
{
    cin>>N>>K;
    // a = n!, b = k!(n-k)!
    long long a=1, b=1; 
    
    for(long long i=1;i<=N;++i)
    {
        a*=i;
        a%=MOD;
    }
    for(long long i=1;i<=K;++i)
    {
        b*=i;
        b%=MOD;
    }
    for(long long i=1;i<=N-K;++i)
    {
        b*=i;
        b%=MOD;
    }
    
    long long b2=pow(b,MOD-2);
    long long ret=a*b2;
    ret%=MOD;
    cout<<ret<<endl;
    return 0;
}

참조

• 위키피디아 이항 정리
• 네이버 분리수거장 블로그
• 위키피디아 페르마의 소정리