Submit Info #2606

Problem Lang User Status Time Memory
Montmort Number cpp ei1333 AC 93 ms 13.91 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.67 MiB
example_01 AC 2 ms 0.67 MiB
max_00 AC 93 ms 13.53 MiB
max_01 AC 85 ms 13.67 MiB
max_02 AC 84 ms 13.91 MiB
random_00 AC 37 ms 5.55 MiB
random_01 AC 41 ms 6.42 MiB
random_02 AC 51 ms 8.30 MiB
random_03 AC 39 ms 6.30 MiB
random_04 AC 69 ms 11.17 MiB

#include <bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 998244353; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } template< typename T > vector< T > montmort(int N) { vector< T > dp(N + 1); for(int k = 2; k <= N; k++) { dp[k] = dp[k - 1] * k; if(k & 1) dp[k] -= 1; else dp[k] += 1; } return dp; } struct ArbitraryModInt { int x; ArbitraryModInt() : x(0) {} ArbitraryModInt(int64_t y) : x(y >= 0 ? y % mod() : (mod() - (-y) % mod()) % mod()) {} static int &mod() { static int mod = 0; return mod; } static int set_mod(int md) { mod() = md; } ArbitraryModInt &operator+=(const ArbitraryModInt &p) { if((x += p.x) >= mod()) x -= mod(); return *this; } ArbitraryModInt &operator-=(const ArbitraryModInt &p) { if((x += mod() - p.x) >= mod()) x -= mod(); return *this; } ArbitraryModInt &operator*=(const ArbitraryModInt &p) { unsigned long long a = (unsigned long long) x * p.x; unsigned xh = (unsigned) (a >> 32), xl = (unsigned) a, d, m; asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod())); x = m; return *this; } ArbitraryModInt &operator/=(const ArbitraryModInt &p) { *this *= p.inverse(); return *this; } ArbitraryModInt operator-() const { return ArbitraryModInt(-x); } ArbitraryModInt operator+(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) += p; } ArbitraryModInt operator-(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) -= p; } ArbitraryModInt operator*(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) *= p; } ArbitraryModInt operator/(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) /= p; } bool operator==(const ArbitraryModInt &p) const { return x == p.x; } bool operator!=(const ArbitraryModInt &p) const { return x != p.x; } ArbitraryModInt inverse() const { int a = x, b = mod(), u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ArbitraryModInt(u); } ArbitraryModInt pow(int64_t n) const { ArbitraryModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ArbitraryModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ArbitraryModInt &a) { int64_t t; is >> t; a = ArbitraryModInt(t); return (is); } }; int main() { int N, M; cin >> N >> M; ArbitraryModInt::set_mod(M); auto ret = montmort< ArbitraryModInt >(N); ret.erase(begin(ret)); cout << ret << endl; }