Submit Info #2165

Problem Lang User Status Time Memory
Montmort Number cpp beet AC 86 ms 13.92 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
example_01 AC 1 ms 0.71 MiB
max_00 AC 86 ms 13.52 MiB
max_01 AC 81 ms 13.67 MiB
max_02 AC 79 ms 13.92 MiB
random_00 AC 35 ms 5.57 MiB
random_01 AC 36 ms 6.42 MiB
random_02 AC 48 ms 8.30 MiB
random_03 AC 33 ms 6.30 MiB
random_04 AC 64 ms 11.17 MiB

#include <assert.h> #include <stdint.h> #include <iostream> #include <algorithm> #include <vector> using namespace std; // number of permutations with p_i != i template<typename T> struct Montmort{ using ll = long long; vector<T> dp; Montmort(int n,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];} }; // https://judge.yosupo.jp/problem/montmort_number_mod int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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; }