Submit Info #2178

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
example_01 AC 1 ms 0.72 MiB
max_00 AC 86 ms 13.55 MiB
max_01 AC 82 ms 13.67 MiB
max_02 AC 78 ms 13.92 MiB
random_00 AC 32 ms 5.55 MiB
random_01 AC 36 ms 6.42 MiB
random_02 AC 48 ms 8.30 MiB
random_03 AC 35 ms 6.35 MiB
random_04 AC 65 ms 11.17 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/montmort_number_mod" #include<bits/stdc++.h> using namespace std; #define call_from_test #ifndef call_from_test #include<bits/stdc++.h> using namespace std; #endif //BEGIN CUT HERE struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #ifndef call_from_test #include<bits/stdc++.h> 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; 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];} }; //END CUT HERE #ifndef call_from_test #define call_from_test #include "../math/extgcd.cpp" #undef call_from_test // montmort signed ARC009_C(){ using ll = long long; ll n,k; scanf("%lld %lld",&n,&k); const int MOD = 1777777777; int ans=Montmort<ll>(k,MOD)[k]; int dom=1; for(int i=0;i<k;i++){ ans=(ll)ans*((n-i)%MOD)%MOD; dom=(ll)dom*(i+1)%MOD; } ans=(ll)ans*mod_inverse<ll>(dom,MOD)%MOD; printf("%d\n",ans); return 0; } /* verified on 2019/12/18 https://atcoder.jp/contests/arc009/tasks/arc009_3 */ signed main(){ ARC009_C(); return 0; } #endif #undef call_from_test signed main(){ 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; }