(13977) 이항 계수와 쿼리

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

단계별로 풀어보기

45단계(수학 2) 4번째

 

 

 

이항 계수 3과 같은 문제인데 입력이 한 번이 아니라 m번 들어온다.

페르마의 소정리를 이용해 이항 계수 계산을 로그 시간복잡도로 최적화하는 부분은 이미 구현했고, n과 k가 바뀔 때마다 대입해야 하는 팩토리얼 값이 달라지므로 팩토리얼 값을 미리 전처리하여 풀면 된다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  long factorial[4000001]={1,};
  
  for(int i=1;i<=4000000;i++)  factorial[i]= (factorial[i-1]*i)%p;
  
  auto power= [](long base, long expo) -> long {
    long res= 1;
    
    while(expo){
      if(expo&1)  res= (res*base)%p;
      base= (base*base)%p;
      expo/= 2;
    }
    
    return res;
  };
  
  int m;
  
  cin >> m;
  
  while(m--){
    int n, k;
    
    cin >> n >> k;
    
    long u= factorial[n];
    long d= power((factorial[k]*factorial[n-k])%p, p-2);
    
    cout << (u*d)%p << "\n";
  }
  
  return 0;
}