BOJ 11401번 :: 이항 계수 3

#문제

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

11401번: 이항 계수 3

 

#작성 코드

#include <iostream>
using namespace std;
 
int mod = 1000000007;
 
long long int power(long long int a, long long int b){
    //a의 b제곱을 구하자
    long long result = 1;
    while( b>0 ){
        if( b%2 ){
            result  = (result*a)%mod;
        }
        
        a = (a*a)%mod;
        b/=2;
    }
    return result;
}
 
long long int comb(long long int n, long long int k){
    long long int facn = 1;
    long long int other = 1;
    
    // n!의 modulo 연산 결과 facn에 저장 
    for(long long int i=1; i<=n; i++){
        facn = (facn*i)%mod;
    }
    
    // k!의 modulo 연산 결과 other에 저장 
    for(long long int i=1; i<=k; i++){
        other = (other*i)%mod;
    }
    // (n-k)!의 modulo 연산 결과 other에 누적 저장. 
    for(long long int i=1; i<=n-k; i++){
        other = (other*i)%mod;
    }
    
    // n!*( k!(n-k)! )^mod-2의 modulo연산 결과 리턴. 
    return (facn*power(other, mod-2))%mod;
}
 
int main(){
    long long int n, k;
    cin>>n>>k;
    cout<<comb(n,k);
    return 0;
} 

##

단순히 n! / ( k! * (n-k)! ) 으로 계산하면

나눗셈에 대한 modulo 연산 분배법칙은 성립하지 않기 때문에,

( k! * (n-k)! )의 곱셈에 대한 역원을 이용해야 한다.   -> 페르마의 소정리 이용.

a(정수)와 p(소수)가 서로소일때 a^p % p = a가 성립한다.

a^p-1 % p = 1

a * a^p-2 % p = 1

=> a의 곱셈에 대한 역원은 a^p-2이다.

=> a^-1과 a^p-2의 modulo p 연산에 대한 결과가 같다.

 

=> ( n! * ( k! * (n-k)! )^-1 ) % p 와 ( n! * ( k! * (n-k)! )^p-2 ) % p  두 식의 결과가 동일하다.

나눗셈에 대한 modulo 연산을 곱셈으로 고쳐서 해결할 수 있다.

 

• 단계별로 풀기 - 분할정복 카테고리에 있던 문제인데, 어떻게 분할정복해서 푸는것인지는 아직 이해 못했다......