test/yosupo/montmort_number_mod.test.cpp

• View this file on GitHub
• Last update: 2020-11-13 17:57:07+09:00
• Problem: https://judge.yosupo.jp/problem/montmort_number_mod

Depends on

• mod/montmort.cpp

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/montmort_number_mod

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../mod/montmort.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  Montmort<int> mm(n,m);
  for(int i=1;i<=n;i++){
    if(i) cout<<" ";
    cout<<mm[i];
  }
  cout<<endl;
  return 0;
}

#line 1 "test/yosupo/montmort_number_mod.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/montmort_number_mod

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "mod/montmort.cpp"

#line 3 "mod/montmort.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// number of permutations with p_i != i
template<typename T>
struct Montmort{
  using ll = long long;
  vector<T> dp;

  // MOD can be composite numbers
  Montmort(int n,const int MOD):dp(n+1,0){
    for(int k=2;k<=n;k++){
      dp[k]=(ll)dp[k-1]*k%MOD;
      if(~k&1) dp[k]+=1;
      else dp[k]+=MOD-1;
      if(dp[k]>=MOD) dp[k]-=MOD;
    }
  }

  T operator[](int n){return dp[n];}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 8 "test/yosupo/montmort_number_mod.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  Montmort<int> mm(n,m);
  for(int i=1;i<=n;i++){
    if(i) cout<<" ";
    cout<<mm[i];
  }
  cout<<endl;
  return 0;
}

Back to top page