백준 이항계수3 문제풀이

지난번에 페르마의 소정리(https://wondangcom.com/689) 에 대해서 올려 드린 적이 있었는데요.

백준문제중 이항계수3(https://www.acmicpc.net/problem/11401) 이라는 문제를 풀다가 페르마의 소정리를 이용해서 풀이를 하기에 페르마의 소정리를 정리해 보았었습니다.

 

오늘은 백준문제중 이항계수3 이라는 문제를 페르마의 소정리를 이용해서 어떤 식으로 풀어 나가는지 확인해 보겠습니다.

 

자연수 n과 k 가 주어졌을때 이항계수를 구하는 문제는 nCk 와 같이 구하면 되고

이것을 식을 이용해 나타내면

n! / (k! * (n-k)! ) 으로 나타낼 수가 있습니다.

하지만 이항계수3 의 문제는 n이 400,000 개의 데이터가 들어 오는데요...

이때 데이터를 모두 계산 후에 1,000,000,0007 으로 나눈 나머지를 출력하라고 하는데요.

문제는 n! / (k! * (n-k)! ) 을 모두 계산 한 후에 1,000,000,0007 으로 나누어야 하는데요.

( 분수 계산은 n! / (k! * (n-k)! ) mod 1,000,000,0007 을 (n! mod 1,000,000,0007) / (k! mod 1,000,000,0007 * (n-k) ! mod 1,000,000,0007) ) 과 같은 형태로 분자 분모에 나누어서 적용하지 못하는 것이 문제가 됩니다.)

그래서 여기서 페르마의 소정리를 이용하게 되는데요.

페르마의 소정리는

a의 (p-1)승 ≡ 1(mod p)

이라는 공식을 이용하는 것입니다.

즉 우리가 구하는 공식을 a = n! , b = k! *(n-k)! 으로 놓는 다고 하면

(a/b) % 1,000,000,0007 이 되며 이것을 다시 표현하면 a * b(-1 승) % 1,000,000,0007 과 같이 표현이 가능합니다.

여기에서 다음과 같은 공식은 성립하지 않습니다.

a % 1,000,000,0007  * b(-1승) % 1,000,000,0007 

b(-1승) 이 분수이기 때문입니다.

따라서 페르마의 소정리를 이용하면

a(p-1 승)≡ 1(mod p)  이므로

a * b(-1 승) % p (여기에서 p는  1,000,000,0007) 을 구하면 됨으로 다음과 같이 식을 변형합니다.

=> a * b(-1승) * 1 % p

=> a * b(-1승) * b(p-1 승) % p

=> a * b(p-2 승) % p 와  같이 표현 가능하고요.

이것은 결국 다음과 같이 계산이 가능합니다.

=> (a % p) * (b(p-2승) %p) % p

(여기서 b(p-2승) 은 분수가 아니기 때문에 곱에서는 mod 의 분배법칙이 성립되기 때문입니다.)

 

이것을 소스로 구현해 보면 다음과  같습니다.

#include <iostream>
using namespace std;
#define P 1000000007LL
long long fac[4000001];
int main()
{
    int n,k;
    cin >> n >> k;
    fac[0]=1;
    fac[1]=1;
    //factorial 구하기
    for(int i=2; i<=n;i++) fac[i] = (fac[i-1] * i) % P;
    //(a%P * b(p-2승) % P) % P 를 구하면 된다.
    long long bVal = (fac[k]*fac[n-k]) % P;
    int index = P-2;
    //b(P-2승) 값을 구하자.
    long long resVal = 1;
    while(index > 0)
    {
        if(index % 2) //인덱스 값이 홀수이면 index
        {
            resVal *= bVal;  //index 값이 홀수이면 bVal을 한번 곱해주자.
            resVal %= P;
        }
        bVal = bVal * bVal;
        //bVal 값을 제곱승 한다.
        //2의 10승인 경우를 계산하면  (2 * 2) * (2 * 2) 를 하게 되면 2의 4승이 되는 원리를 이용한다.
        bVal %= P;
        index /= 2;
    }
    cout << ((fac[n] % P) * (resVal % P)) % P << endl;
    return 0;
}