(11401) 이항 계수 3

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

단계별로 풀어보기

24단계(분할 정복) 5번째

 

 

 

이 문제를 풀려면 알고리즘 지식 뿐만 아니라 '수학 지식'도 필요하다. 정확히는 페르마의 소정리에 대해 알아야 한다.

간단히 말하면 소수 p에 대해 a^p ≡ a (mod p), a와 p가 서로소라면 a^(p-1) ≡ 1 (mod p)라는 것이다.

이것을 어떻게 이용하느냐? 이항 계수를 A/B라고 하자.

우리가 원하는 건 A/B mod p이다. 이때 A/B = A*B^-1이고, B^-1 ≡ B^(p-2) (mod p)이므로

거듭제곱 공식을 이용해 원하는 값을 구할 수 있다. A와 B는 팩토리얼로 나타내는 이항 계수 공식으로 찾으면 된다.

 

설명이 조금 부실하긴 하지만, 수학이 아니라 알고리즘이 목적이므로 중요하게 다룰 필요는 없다고 생각한다. 다만 조금 심화된 문제에서 이런 정수론 지식같은 건 지엽적이라고 넘어가기엔 꽤 자주 보이기 때문에 본인 목표에 따라 배울 필요도 있다.

 

 

 

#include <iostream>
using namespace std;
#define p 1000000007

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

int main() {
  long n, k;
  
  cin >> n >> k;
  
  long a= 1, b= 1;
  
  for(int i=n;i>n-k;i--)  a= (a*i)%p;
  for(int i=1;i<=k;i++)  b= (b*i)%p;
  
  cout << (a*power(b, p-2))%p;
  
  return 0;
}