(11402) 이항 계수 4

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

단계별로 풀어보기

56단계(수학 3) 1번째

 

 

이전에 제수가 소수인 경우에는 페르마의 소정리를 이용하여 이항 계수를 O(log M)에 구할 수 있었지만, 이 방법은 모듈러 연산이 된 팩토리얼 값이 필요해 O(N)의 전처리가 필요하다. 따라서 N의 값이 크다면 이 방법을 쓸 수 없다.

이럴 땐 뤼카의 정리를 써야 한다. N과 K를 M진법으로 나타냈을 때 n_1n_2...n_p(M)와 k_1k_2...k_p(M)가 된다고 하자. M진법 K의 자리수가 N의 자리수보다 작다면 앞쪽에 0을 붙여 자리수를 맞춰주면 된다. 이때 C(N, K) ≡ C(n_1, k_1)*C(n_2, k_2)*...*C(n_p, k_p) (mod M)가 성립한다. 만약 n_i<m_i라면 해당 이항 계수 값은 0이고 C(N, K)도 0이 된다.

 

 

 

#include <iostream>
using namespace std;
typedef unsigned long ul;

int power(int base, int expo, int p){
  int res= 1;
  base%= p;
  
  while(expo){
    if(expo&1)  res= (res*base)%p;
    base= (base*base)%p;
    expo/= 2;
  }
  
  return res;
}

int main() {
  int fac[2000]= {1, };
  long n, k, m, ans =1;

  cin >> n >> k >> m;

  for(int i=1;i<=m;i++){
    fac[i]= (fac[i-1]*i)%m;
  }
  
  while(n&&k){
    int nm= n%m, km= k%m;
    if(km>nm){
      ans= 0;
      break;
    }
    ans= (ans*fac[nm]*power((fac[km]*fac[nm-km])%m, m-2, m))%m;
    n/= m;
    k/= m;
  }

  cout << ans;

  return 0;
}