Submit Info #13499

Problem Lang User Status Time Memory
Montmort Number cpp samzhang AC 79 ms 10.05 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.72 MiB
example_01 AC 4 ms 0.70 MiB
max_00 AC 79 ms 9.68 MiB
max_01 AC 74 ms 9.80 MiB
max_02 AC 73 ms 10.05 MiB
random_00 AC 28 ms 4.12 MiB
random_01 AC 35 ms 4.71 MiB
random_02 AC 45 ms 6.05 MiB
random_03 AC 35 ms 4.72 MiB
random_04 AC 60 ms 8.17 MiB

#pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast") //#pragma GCC optimize(3) //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC target("sse3","sse2","sse") //#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3") //#pragma GCC target("f16c") //#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector") //#pragma GCC diagnostic error "-fwhole-program" //#pragma GCC diagnostic error "-fcse-skip-blocks" //#pragma GCC diagnostic error "-funsafe-loop-optimizations" //#pragma GCC diagnostic error "-std=c++14" #include "bits/stdc++.h" #include "ext/pb_ds/tree_policy.hpp" #include "ext/pb_ds/assoc_container.hpp" #define PB push_back #define PF push_front #define LB lower_bound #define UB upper_bound #define fr(x) freopen(x,"r",stdin) #define fw(x) freopen(x,"w",stdout) #define REP(x, l, u) for(ll x = l;x<u;x++) #define RREP(x, l, u) for(ll x = l;x>=u;x--) #define complete_unique(a) a.erase(unique(begin(a),end(a)),end(a)) #define mst(x, a) memset(x,a,sizeof(x)) #define all(a) begin(a),end(a) #define rall(a) rbegin(a),rend(a) #define PII pair<int,int> #define PLL pair<ll,ll> #define MP make_pair #define lowbit(x) ((x)&(-(x))) #define bitcnt(x) (__builtin_popcountll(x)) #define lson (ind<<1) #define rson (ind<<1|1) #define se second #define fi first #define sz(x) ((int)x.size()) #define EX0 exit(0); typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; using namespace __gnu_pbds; //required using namespace std; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef vector<ll> VLL; typedef vector<int> VI; const ll mod = 1e9 + 7; string to_string (string s) { return '"' + s + '"'; } string to_string (const char *s) { return to_string ((string) s); } string to_string (bool b) { return (b ? "true" : "false"); } template<typename A, typename B> string to_string (pair<A, B> p) { return "(" + to_string (p.first) + ", " + to_string (p.second) + ")"; } template<typename A> string to_string (A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string (x); } res += "}"; return res; } void debug_out () { cerr<<endl; } template<typename Head, typename... Tail> void debug_out (Head H, Tail... T) { cerr<<" "<<to_string (H); debug_out (T...); } #ifdef LOCAL #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define dbg(...) {} #endif template<typename T, typename S> inline bool upmin (T &a, const S &b) { return a > b ? a = b, 1 : 0; } template<typename T, typename S> inline bool upmax (T &a, const S &b) { return a < b ? a = b, 1 : 0; } ull twop (ll x) { return 1ULL<<x; } ll MOD (ll a, ll m) { a %= m; if (a < 0)a += m; return a; } ll inverse (ll a, ll m) { a = MOD (a, m); if (a <= 1)return a; return MOD ((1 - inverse (m, a) * m) / a, m); } template<typename T> T sqr (T x) { return x * x; } ll gcd (ll a, ll b) { a = abs (a), b = abs (b); while (b != 0) { a %= b; swap (a, b); } return a; } ll fast (ll a, ll b, ll mod) { a %= mod; if (b < 0)a = inverse (a, mod), b = -b; ll ans = 1; while (b) { if (b & 1)ans = ans * a % mod; a = a * a % mod; b /= 2; } return ans % mod; } namespace NTT { const int mod = 998244353, g = 3; void bit_reverse_swap (VI &a) { int n = sz(a); for (int i = 1, j = n>>1, k; i < n - 1; i++) { if (i < j) swap (a[i], a[j]); for (k = n>>1; j >= k; j -= k, k >>= 1); j += k; } } void NTT (VI &a, int type) { bit_reverse_swap (a); int n = sz (a); for (int i = 2; i <= n; i *= 2) { const auto wi = fast (g, type * (mod - 1) / i, mod); // fp(g, (mod - 1) / i) 是 i 次单位根 for (int j = 0; j < n; j += i) { ll w = 1; for (int k = j, h = i / 2; k < j + h; k++) { int t = w * a[k + h] % mod, u = a[k]; a[k] = (u + t) % mod; a[k + h] = (u - t + mod) % mod; w = w * wi % mod; } } } const ll inv = inverse (n, mod); if (type == -1) for (auto &x : a) x = x * inv % mod; } VI conv (const VI &a, const VI &b, const int n, const int m, const int mod = NTT::mod) { VI _a (begin (a), begin (a) + n); VI _b (begin (b), begin (b) + m); int len = 1; while (len <= n + m - 2) len <<= 1; while (len != lowbit(len)) len += lowbit(len); _a.resize (len), _b.resize (len); NTT (_a, 1), NTT (_b, 1); REP(i, 0, len) _a[i] = (ll) _a[i] * _b[i] % mod; NTT (_a, -1); _a.resize (n + m - 1); return _a; } } namespace Poly { using NTT::mod; using NTT::conv; VI iv ({0, 1}), fac ({1, 1}), facinv ({1, 1}); void init (const int n) { while (sz(iv) <= n) { ll cur = sz(iv); iv.emplace_back ((mod - (ll) mod / cur * iv[mod % cur] % mod)); fac.PB (cur * fac.back () % mod); facinv.PB ((ll)iv.back () * facinv.back () % mod); } } //B(x) ≡ 2C(x) − A(x)C(x)^2 VI inv (const VI &poly) { int n = 1; VI res (1); res[0] = inverse (poly[0], mod); while (n < sz(poly)) { auto new_res = conv (res, res, n, n, mod); new_res = conv (poly, new_res, min (2 * n, sz(poly)), sz(new_res), mod); res.resize (2 * n, 0); REP(i, 0, 2 * n) { res[i] = (2ll * res[i] - (i < sz(new_res) ? new_res[i] : 0) + mod) % mod; } n *= 2; } res.resize (sz(poly)); return res; } VI integrate (const VI &poly) { init (sz(poly)); VI res (sz(poly), 0); REP(i, 1, sz (res)) { res[i] = poly[i - 1] * (ll) iv[i] % mod; } return res; } VI differentiate (const VI &poly) { VI res (sz(poly), 0); REP(i, 0, sz (res) - 1) { res[i] = poly[i + 1] * ll (i + 1) % mod; } return res; } VI log (const VI &poly) { auto res = integrate (conv (differentiate (poly), inv (poly), sz(poly), sz(poly), mod)); res.resize (sz(poly)); return res; } // g ≡ (1 − ln(g0) + f)g0 VI exp (const VI &poly) { int n = 1; VI res (1, 1); VI tmp; while (n < sz(poly)) { tmp = res; tmp.resize (2 * n, 0); tmp = log (tmp); REP(i, 0, 2 * n) { tmp[i] = (ll (i == 0) - tmp[i] + (i < sz(poly) ? poly[i] : 0) + mod) % mod; } res = conv (res, tmp, n, 2 * n, mod); res.resize (2 * n, 0); n *= 2; } res.resize (sz(poly)); return res; } // k < mod VI power (const VI &poly, const ll k) { auto low = find_if (all(poly), [] (const int x) { return x != 0; }); if (low == end (poly))return VI (sz(poly), 0); ll padding = (low - begin (poly)) * k; if (padding >= sz(poly))return VI (sz(poly), 0); VI tmp (low, end (poly)); ll inv = inverse (*low, mod); for (auto &x:tmp) x = x * inv % mod; tmp = log (tmp); for (auto &x:tmp) x = x * (k % mod) % mod; tmp = exp (tmp); ll pw = fast (inv, -k, mod); for (auto &x:tmp) x = x * pw % mod; if (padding) { VI zeros (padding, 0); tmp.insert (tmp.begin (), all(zeros)); } tmp.resize (sz(poly), 0); return tmp; } ll modSqrt (ll a, ll p) { auto isSquare = [&] (ll a, ll p) { return fast (a, (p - 1) / 2, p) == 1; }; if (a == 0) return 0; if (p == 2) return a; if (!isSquare (a, p)) return -1; ll b = 2; while (isSquare ((b * b - a + p) % p, p)) b++; ll w = (b * b - a + p) % p; auto mul = [&] (PLL u, PLL v) { ll a = (u.first * v.first + u.second * v.second % p * w) % p; ll b = (u.first * v.second + u.second * v.first) % p; return MP (a, b); }; // (b + sqrt(b^2-a))^(p+1)/2 ll e = (p + 1) / 2; auto ret = MP (1, 0); auto v = MP (b, 1); while (e > 0) { if (e & 1) ret = mul (ret, v); v = mul (v, v); e /= 2; } return ret.first; } VI sqrt (VI poly) { const int len = sz(poly); init (2); const auto low = find_if (all(poly), [] (const int x) { return x != 0; }); if (low == end (poly))return VI (sz(poly), 0); int padding = (low - begin (poly)); if (padding & 1) return VI (1, -1); padding >>= 1; poly = VI (low, end (poly)); VI res (1); res[0] = modSqrt (poly[0], mod); if (res[0] == -1)return res; res[0] = min (res[0], mod - res[0]); int n = 1; while (n < len) { n *= 2; res.resize (n, 0); auto other = conv (poly, inv (res), min (2 * n, sz(poly)), n, mod); REP(i, 0, n) { res[i] = (res[i] + other[i]) * ll (iv[2]) % mod; } } if (padding) { VI zeros (padding, 0); res.insert (res.begin (), all(zeros)); } res.resize (len, 0); return res; } // pair<VI, VI> divmod (VI f, VI g) { auto removeTrailingZeros = [] (VI &poly) { while (sz(poly) and poly.back () == 0)poly.pop_back (); }; removeTrailingZeros (f); removeTrailingZeros (g); assert(sz (g) > 0); const int n = sz(f) - 1, m = sz(g) - 1; if (n < m)return MP (VI (), f); auto rev = [] (VI poly) { reverse (all(poly)); return poly; }; auto rg = rev (g); rg.resize (n, 0); auto q = (conv (rev (f), inv (rg), sz(f), sz(rg))); q.resize (n - m + 1, 0); q = rev (q); auto prod = conv (g, q, sz(g), sz(q)); auto r = f; REP(i, 0, sz (r))r[i] = (r[i] - prod[i] + mod) % mod; r.resize (m, 0); removeTrailingZeros (r); return MP (q, r); } VI shift (const VI &poly, const int n) { init (sz(poly)); VI a (sz(poly)), b (sz(poly)); REP(i, 0, sz (a))a[i] = (ll) fac[i] * poly[i] % mod; for (int i = 0, prod = 1; i < sz(poly); i++, prod = (ll) prod * n % mod) { b[i] = (ll) facinv[i] * prod % mod; } VI res (sz(poly)); reverse (all(b)); a = conv (a, b, sz(a), sz(b)); REP(i, 0, sz (res)) { res[i] = (ll) a[i + sz(poly) - 1] * facinv[i] % mod; } return res; } // TODO: Multi Point Eval } namespace SOLVE { void main () { ll n,m;cin>>n>>m; ll ans = 1; REP(i,1,n+1){ ans *= i; if(i&1)ans--; else ans ++; ans = MOD(ans,m); cout<<ans<<" "; } } } signed main () { #ifdef LOCAL fr("/Users/zhangqingchuan/Desktop/cp/cp/input.txt"); fw("/Users/zhangqingchuan/Desktop/cp/cp/output.txt"); #endif ios::sync_with_stdio (false); cin.tie (nullptr); cout.tie (nullptr); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { // cout<<"Case #"<<i<<": "; SOLVE::main (); } // clock_t st = clock(); // while(clock() - st < 3.0 * CLOCKS_PER_SEC){ // // } return 0; }