This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// 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; }