(15718) 돌아온 떡파이어

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

단계별로 풀어보기

45단계(수학 2) 5번째

 

 

 

마지막 M일에는 무조건 0그릇의 떡국을 먹어야 하고, M-1일동안 N그릇의 떡국을 먹는다. 이때 하루에 1그릇 이상은 먹어야 하므로 M-1일동안 N-M+1그릇의 떡국을 자유롭게 먹는 경우와 같고, 이는 중복조합 H(M-1, N-M+1)이다.

조합으로 바꾸면 C(N-1, N-M+1)= C(N-1, M-2)이므로 이항 계수를 구하는 문제와 같다.

문제는 100007은 소수가 아니라 97*1031라는 두 소수의 곱으로 이루어진 합성수라 페르마의 소정리를 쓸 수 없다.

따라서 중국인의 나머지 정리를 써야 한다. 또한 이항 계수를 97, 1031로 나눈 값 또한 페르마의 소정리를 쓰기에는 N의 범위가 너무 크기 때문에 뤼카의 정리를 써야 한다.

뤼카의 정리를 쓰는 문제는 수학 3 파트에서나 나오는데, 이 문제도 뤼카의 정리가 거의 필수다. 난이도 조절 실패같다.

 

 

 

#include <iostream>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int fac1[97]= {1, }, fac2[1031]= {1, };
  
  for(int i=1;i<97;i++)  fac1[i]= (fac1[i-1]*i)%97;
  for(int i=1;i<1031;i++)  fac2[i]= (fac2[i-1]*i)%1031;
  
  auto power= [](int base, int expo, int mod) -> int {
    int res= 1;
    
    while(expo){
      if(expo&1)  res= (res*base)%mod;
      base= (base*base)%mod;
      expo/= 2;
    }
    
    return res;
  };
  
  auto lucas= [&](int n, int k, int mod, auto& fac){
    int res= 1;
    
    while(n||k){
      int nm= n%mod, km= k%mod;
      
      if(nm<km)  return 0;
      
      res= (res*fac[nm]*power((fac[km]*fac[nm-km])%mod, mod-2, mod))%mod;
      
      n/= mod;  k/= mod;
    }
    
    return res;
  };
  
  auto inverse= [&](int a, int n){
    long q;
    pair<long, long> r= {a, n};
    pair<long, long> s= {1, 0};
    pair<long, long> t= {0, 1};
    
    while(r.second){
      q= r.first/r.second;
      r= {r.second, r.first-r.second*q};
      s= {s.second, s.first-s.second*q};
      t= {t.second, t.first-t.second*q};
    }
    
    return (s.first+n)%n;
  };
  
  auto crt= [&](int a1, int a2, int n1, int n2){
    return (a1*n2*inverse(n2, n1) + a2*n1*inverse(n1, n2))%100007;
  };
  
  int T;
  
  cin >> T;
  
  while(T--){
    int n, m;
    
    cin >> n >> m;
    
    if(m==1){
      cout << !n << "\n";
      continue;
    }
    
    int a1= lucas(n-1, m-2, 97, fac1);
    int a2= lucas(n-1, m-2, 1031, fac2);
    
    cout << crt(a1, a2, 97, 1031) << "\n";
  }
  
  return 0;
}

 

 

 

이 문제에서 적용되는 중국인의 나머지 정리는 n1=97, n2=1031로 고정이므로 모듈로 역원도 고정이고, 굳이 함수로 구현할 필요 없이 하드코딩으로 값을 계산할 수 있다.

#include <iostream>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int fac1[97]= {1, }, fac2[1031]= {1, };
  
  for(int i=1;i<97;i++)  fac1[i]= (fac1[i-1]*i)%97;
  for(int i=1;i<1031;i++)  fac2[i]= (fac2[i-1]*i)%1031;
  
  auto power= [](int base, int expo, int mod) -> int {
    int res= 1;
    
    while(expo){
      if(expo&1)  res= (res*base)%mod;
      base= (base*base)%mod;
      expo/= 2;
    }
    
    return res;
  };
  
  auto lucas= [&](int n, int k, int mod, auto& fac){
    int res= 1;
    
    while(n||k){
      int nm= n%mod, km= k%mod;
      
      if(nm<km)  return 0;
      
      res= (res*fac[nm]*power((fac[km]*fac[nm-km])%mod, mod-2, mod))%mod;
      
      n/= mod;  k/= mod;
    }
    
    return res;
  };
  
  int T;
  
  cin >> T;
  
  while(T--){
    int n, m;
    
    cin >> n >> m;
    
    if(m==1){
      cout << !n << "\n";
      continue;
    }
    
    int a1= lucas(n-1, m-2, 97, fac1);
    int a2= lucas(n-1, m-2, 1031, fac2);
    
    cout << (a1*36085+a2*63923)%100007 << "\n";
  }
  
  return 0;
}