Submit Info #654

Problem Lang User Status Time Memory
Partition Function cpp ryuhei AC 158 ms 35.67 MiB

ケース詳細
Name Status Time Memory
0_00 AC 143 ms 26.18 MiB
100000_00 AC 148 ms 28.05 MiB
10000_00 AC 144 ms 26.42 MiB
1000_00 AC 147 ms 26.23 MiB
100_00 AC 144 ms 26.19 MiB
1_00 AC 144 ms 26.20 MiB
200000_00 AC 149 ms 29.92 MiB
300000_00 AC 154 ms 31.89 MiB
400000_00 AC 156 ms 33.80 MiB
500000_00 AC 158 ms 35.67 MiB
example_00 AC 145 ms 26.18 MiB

#include <unistd.h> #include <cassert> struct IO { static const int bufsize=1<<24; char ibuf[bufsize], obuf[bufsize]; char *ip, *op; IO(): ip(ibuf), op(obuf) { for(int t = 0, k = 0; (k = read(STDIN_FILENO, ibuf+t, sizeof(ibuf)-t)) > 0; t+=k); } ~IO(){ for(int t = 0, k = 0; (k = write(STDOUT_FILENO, obuf+t, op-obuf-t)) > 0; t+=k); } long long scan_int(){ long long x=0; bool neg=false; for(;*ip<'+';ip++) ; if(*ip=='-'){ neg=true; ip++;} else if(*ip=='+'){ ip++;} for(;*ip>='0';ip++){ x = 10*x+*ip-'0'; } if(neg) x = -x; return x; } void put_int(long long x, char c=0){ static char tmp[20]; if(x==0){ *op++ = '0'; } else { int i; if(x<0){ *op++ = '-'; x = -x; } for(i=0; x; i++){ tmp[i] = x % 10; x /= 10; } for(i--; i>=0; i--) *op++ = tmp[i]+'0'; } if(c) *op++ = c; } void put_double(double x, char c=0){ unsigned y; const int mask = (1<<24) - 1; put_int(x); *op++ = '.'; x = x - (int) x; if(x < 0) x = -x; y = x * (1<<24); for(int i=0;i<7;i++){ y *= 10; *op++ = '0' + (y>>24); y &= mask; } } inline char scan_char(){ return *ip++; } inline void put_char(char c){ *op++ = c; } inline char *scan_string(){ char *s = ip; while(*ip++!='\n'){} *(ip-1)='\0'; return s;} inline void put_string(char *s, char c=0){ while(*s) *op++=*s++; if(c) *op++=c;} }; template <int MOD> struct Mint { int n; static constexpr int s = __builtin_ctz(MOD - 1); static constexpr int q = MOD >> __builtin_ctz(MOD - 1); static constexpr Mint<MOD> c0 = []() constexpr { int z = 0; for(z = 2; z < MOD; z++){ if(Mint<MOD>(z).pow((MOD - 1) / 2) != 1) break; } return Mint<MOD>(z).pow(MOD >> __builtin_ctz(MOD-1)); }(); constexpr Mint(int n = 0): n(n) {} constexpr Mint<MOD> operator -(){ return n ? MOD - n: 0; } constexpr void operator -= (const Mint<MOD> &rhs){ if(n >= rhs.n) n -= rhs.n; else n = MOD - (rhs.n - n); } constexpr void operator += (const Mint<MOD> &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; } constexpr void operator *= (const Mint<MOD> &rhs){ n = (long long) n * rhs.n % MOD; } constexpr void operator /= (const Mint<MOD> &rhs){ n = (long long) n * rhs.inv().n % MOD; } constexpr bool operator == (const Mint<MOD> &rhs) const { return n == rhs.n; } constexpr bool operator != (const Mint<MOD> &rhs) const { return n != rhs.n; } friend constexpr Mint<MOD> operator - (const Mint<MOD> &lhs, const Mint<MOD> &rhs){ Mint<MOD> r = lhs; r -= rhs; return r; } friend constexpr Mint<MOD> operator + (const Mint<MOD> &lhs, const Mint<MOD> &rhs){ Mint<MOD> r = lhs; r += rhs; return r; } friend constexpr Mint<MOD> operator * (const Mint<MOD> &lhs, const Mint<MOD> &rhs){ Mint<MOD> r = lhs; r *= rhs; return r; } friend constexpr Mint<MOD> operator / (const Mint<MOD> &lhs, const Mint<MOD> &rhs){ Mint<MOD> r = lhs; r /= rhs; return r; } constexpr Mint<MOD> pow(int n) const { Mint<MOD> r = 1; Mint<MOD> x = *this; for(; n; n >>= 1){ if(n & 1) r *= x; x *= x; } return r; } constexpr Mint<MOD> inv() const { return pow(MOD - 2); } Mint<MOD> sqrt() const { if(n == 0) return 0; if(pow((MOD - 1) / 2) != 1){ return MOD; } int m = s; Mint<MOD> c = c0; Mint<MOD> t = pow(q); Mint<MOD> r = pow((q + 1) / 2); while(t != 1){ int i; Mint<MOD> u = t * t; for(i = 1; u != 1; i++) u = u * u; int j = 1; int k = m - i - 1; while(k--){ j = j + j; if(j >= MOD) j -= MOD; } Mint<MOD> b = c.pow(j); m = i; c = b * b; t = t * c; r = r * b; } return r; } }; template <int MOD, int N> struct Minv { Mint<MOD> inv[N+1]; constexpr Minv(): inv() { inv[1] = 1; for(int i = 2; i <= N; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i]; } constexpr Mint<MOD> operator[](int i) const { return inv[i]; } }; template <int MOD, int K> struct FFT { Mint<MOD> w[1<<(K-1)]; Mint<MOD> y[1<<(K-1)]; Mint<MOD> v[1<<(K-2)]; static constexpr Mint<MOD> root = []() constexpr { bool sieve[1<<16] = {}; int factors[1<<16] = {}; int fs = 0; int t = MOD - 1; int i = 0; for(; t % 2 == 0; t /= 2) i++; factors[fs++] = (MOD - 1) / 2; if(i < K) return Mint<MOD>(0); for(int i = 3; (long long) i * i < t; i += 2){ if(!sieve[i]){ for(int j = 3 * i; (long long) j * j < t; j += 2 * i) sieve[j] = true; if(t % i == 0){ factors[fs++] = (MOD - 1) / i; do { t /= i; } while(t % i == 0); } } } if(t != 1) factors[fs++] = (MOD - 1) / t; for(int i = 2; i < MOD; i++){ int j = 0; for(j = 0; j < fs; j++){ if(Mint<MOD>(i).pow(factors[j]) == 1) break; } if(j == fs) return Mint<MOD>(i).pow(MOD >> K); } return Mint<MOD>(0); }(); FFT(): w(), y(), v() { constexpr int m = 1 << K; static_assert(root != 0); w[m / 4] = root; y[m / 4] = root.inv(); for(int j = m / 4; j > 1; j >>= 1){ w[j / 2] = w[j] * w[j]; y[j / 2] = y[j] * y[j]; } w[0] = y[0] = 1; for(int j = 2; j < m / 2; j <<= 1){ for(int i = 1; i < j; i++){ w[j + i] = w[j] * w[i]; y[j + i] = y[j] * y[i]; } } v[0] = 1; for(long unsigned int i = 1; i < sizeof(v)/sizeof(v[0]); i++) v[i] = root * v[i - 1]; } void fft(Mint<MOD> *A, int k = K) const { int u = 1; int v = 1 << (k-1); for(int i=k;i>0;i--){ for(int jh=0;jh<u;jh++){ Mint<MOD> wj = w[jh]; for(int j = jh << i, je = j+v;j<je; j++){ Mint<MOD> Ajv = wj * A[j+v]; A[j+v] = A[j] - Ajv; A[j] = A[j] + Ajv; } } u <<= 1; v >>= 1; } } void ifft(Mint<MOD> *A, int k = K) const { int u = 1 << (k-1); int v = 1; for(int i=1;i<=k;i++){ for(int jh=0;jh<u;jh++){ Mint<MOD> wj = y[jh]; for(int j = jh << i, je = j+v;j<je; j++){ Mint<MOD> Ajv = A[j] - A[j+v]; A[j] = A[j] + A[j+v]; A[j+v] = wj * Ajv; } } u >>= 1; v <<= 1; } } }; template <int MOD, int K> struct Poly { Mint<MOD> c[1 << (K + 1)]; inline static FFT<MOD, K + 1> fft; inline static Minv<MOD, (1 << K) - 1> minv; // static constexpr auto minv = Minv<MOD, (1 << K) - 1>(); // static constexpr auto fft = FFT<MOD, K + 1>(); void operator += (const Poly<MOD, K>& rhs){ for(int i = 0; i < (1 << K); i++) c[i] += rhs.c[i]; } void operator -= (const Poly<MOD, K>& rhs){ for(int i = 0; i < (1 << K); i++) c[i] -= rhs.c[i]; } void operator *= (const Poly<MOD, K>& rhs){ Mint<MOD> D[1 << (K + 1)] = {}; for(int i = 0; i < (1 << (K + 0)); i++) D[i] = rhs.c[i]; fft.fft(c); fft.fft(D); const Mint<MOD> t = Mint<MOD>((MOD+1)/2).pow(K+1); for(int i = 0; i < (1 << (K + 1)); i++) c[i] *= D[i] * t; fft.ifft(c); } // Graeffe's method: 2 M(n) Poly<MOD, K> invG() const { assert(c[0] != 0); Mint<MOD> d[1 << (K + 2)]; Mint<MOD> c0inv = Mint<MOD>(c[0]).pow(MOD-2); for(int i = 0; i < (1 << K); i++) d[i] = c[i] * c0inv; fft.fft(d); int k = K + 1; Mint<MOD> *Q = d; Mint<MOD> im = Mint<MOD>((1+MOD)/2).pow(k-1); while(k>1){ Mint<MOD> *QQ = Q + (1<<k); for(int i = 0; i < (1 << (k - 1)); i++) QQ[i] = Q[2*i] * Q[2*i+1]; Q = QQ; k--; fft.ifft(Q, k); for(int i = 0; i < (1 << (k - 1)); i++){ Q[i] = Q[i] * im; Q[(1 << (k - 1)) + i] = 0; } im += im; fft.fft(QQ, k); } int normal = 0; while(Q > d){ Mint<MOD> *QQ = Q - (1 << (k + 1)); for(int i = 0; i < (1 << k); i++){ Mint<MOD> tmp0 = QQ[2*i] * Q[i]; Mint<MOD> tmp1 = QQ[2*i+1] * Q[i]; QQ[2*i] = tmp1; QQ[2*i+1] = tmp0; } k++; Q = QQ; fft.ifft(Q, k); for(int i = (1 << (k - 1)); i < (1 << k); i++) Q[i] = 0; fft.fft(Q, k); normal += k; } fft.ifft(Q, k); normal += k; Mint<MOD> iim = Mint<MOD>((1+MOD)/2).pow(normal) * c0inv; Poly<MOD, K> r; for(int i = 0; i < (1 << K); i++) r.c[i] = d[i] * iim; return r; } // Newton 2 M(n) Poly<MOD, K> inv2() const { assert(c[0] != 0); Mint<MOD> d[1 << (K + 1)]; Mint<MOD> ee[1 << (K + 1)]; Poly<MOD, K> r; r.c[0] = c[0].inv(); int y = (MOD+1)/2; if(y&1) y += MOD; y /= 2; Mint<MOD> im = MOD - y; for(int i = 0; i < K; i++){ for(int j = 0; j < (1 << (i + 1)); j++) d[j] = c[j]; fft.fft(d, i + 2); for(int j = 0; j < (1 << i); j++) ee[j] = r.c[j]; for(int j = (1 << i); j < (1 << (i + 1)); j++) ee[j] = 0; fft.fft(ee, i + 2); for(int j = 0; j < (1 << (i + 2)); j++) d[j] *= ee[j] * ee[j]; fft.ifft(d, i + 2); for(int j = 1 << i; j < (1 << (i + 1)); j++) r.c[j] = d[j] * im; if(im.n&1) im.n += MOD; im.n /= 2; } return r; } // Newton (1 + 2/3) M(n) = 5/3 M(n) Poly<MOD, K> inv() const { assert(c[0] != 0); Mint<MOD> d[1 << (K + 1)]; Mint<MOD> ee[1 << (K + 1)]; Poly<MOD, K> r; r.c[0] = c[0].inv(); int y = (MOD+1)/2; if(y&1) y += MOD; y /= 2; Mint<MOD> im = MOD - y; for(int i = 0; i < K; i++){ for(int j = 0; j < (1 << (i + 1)); j++) d[j] = c[j]; fft.fft(d, i + 1); for(int j = 0; j < (1 << i); j++) ee[j] = r.c[j]; fft.fft(ee, i + 1); for(int j = 0; j < (1 << (i + 1)); j++) d[j] *= ee[j]; fft.ifft(d, i + 1); for(int j = 0; j < (1 << i); j++) d[j] = d[j + (1 << i)], d[j + (1 << i)] = 0; fft.fft(d, i + 1); for(int j = 0; j < (1 << (i + 1)); j++) d[j] *= ee[j]; fft.ifft(d, i + 1); for(int j = 0; j < (1 << i); j++) r.c[j + (1 << i)] = d[j] * im; if(im.n&1) im.n += MOD; im.n /= 2; if(im.n&1) im.n += MOD; im.n /= 2; } return r; } // Newton: 2 M(n) Poly<MOD, K> isqrt() const { assert(c[0] == 1); Mint<MOD> d[1 << (K + 1)]; Mint<MOD> ee[1 << (K + 1)]; Poly<MOD, K> r; r.c[0] = 1; int y = (MOD+1)/2; if(y&1) y += MOD; y /= 2; if(y&1) y += MOD; y /= 2; Mint<MOD> im = MOD - y; for(int i = 0; i < K; i++){ for(int j = 0; j < (1 << (i + 1)); j++) d[j] = c[j]; fft.fft(d, i + 2); for(int j = 0; j < (1 << i); j++) ee[j] = r.c[j]; for(int j = (1 << i); j < (1 << (i + 1)); j++) ee[j] = 0; fft.fft(ee, i + 2); for(int j = 0; j < (1 << (i + 2)); j++) d[j] *= ee[j] * ee[j] * ee[j]; fft.ifft(d, i + 2); for(int j = 1 << i; j < (1 << (i + 1)); j++) r.c[j] = d[j] * im; if(im.n&1) im.n += MOD; im.n /= 2; } return r; } // Newton: (1 + 1/2 + (1/4)*(2/3) + (1/2)*(2/3)) M(n) = 2 M(n) Poly<MOD, K> sqrt() const { assert(c[0] == 1); Poly<MOD, K-1> g; Mint<MOD> d[1 << K] = {}; Mint<MOD> e[1 << (K-1)] = {}; Mint<MOD> f[1 << K] = {}; for(int i = 0; i < (1 << (K - 1)); i++) g.c[i] = d[i] = c[i]; Poly<MOD, K-1> gg = g.isqrt(); fft.fft(d, K); fft.fft(gg.c, K); for(int i = 0; i < (1 << K); i++) f[i] = gg.c[i]; Mint<MOD> im0 = Mint<MOD>((1+MOD)/2).pow(K + 1); Mint<MOD> im1 = im0 + im0; Mint<MOD> im2 = im1 + im1; for(int i = 0; i < (1 << K); i++) gg.c[i] *= d[i] * im1; fft.ifft(gg.c, K); for(int i = 0; i < (1 << (K - 1)); i++) e[i] = gg.c[i]; fft.fft(e, K - 1); for(int i = 0; i < (1 << (K - 1)); i++) e[i] *= e[i] * im2; fft.ifft(e, K - 1); for(int i = 0; i < (1 << (K - 1)); i++) d[i] = c[i + (1 << (K - 1))] + c[i] - e[i]; for(int i = (1 << (K - 1)); i < (1 << K); i++) d[i] = 0; fft.fft(d, K); for(int i = 0; i < (1 << K); i++) d[i] *= f[i] * im0; fft.ifft(d, K); for(int i = 0; i < (1 << (K - 1)); i++) gg.c[i + (1 << (K - 1))] = d[i]; Poly<MOD, K> r; for(int i = 0; i < (1 << K); i++) r.c[i] = gg.c[i]; return r; } // Newton (5/6 + (1/2)*(2/3) + 1 + 2/3) M(n) = 17/6 M(n) Poly<MOD, K> exp() const { assert(c[0] == 0); Mint<MOD> f[1 << K] = {}; Mint<MOD> g[1 << (K-1)] = {}; Mint<MOD> ff[1 << K] = {}; Mint<MOD> gg[1 << K] = {}; Mint<MOD> G[1 << K] = {}; f[0] = 1; f[1] = c[1]; g[0] = 1; G[0] = G[1] = 1; int y = (MOD+1)/2; if(y&1) y += MOD; y /= 2; Mint<MOD> im = y; for(int i = 1; i < K; i++){ for(int j = 0; j < (1 << i); j++) ff[j] = f[j] * im; fft.fft(ff, i + 1); /* for(int j = 0; j < (1 << (i - 1)); j++) gg[j] = g[j]; for(int j = (1 << (i - 1)); j < (1 << i); j++) gg[j] = 0; fft.fft(gg, i + 1); */ for(int j = 0; j < (1 << i); j++) gg[j] = G[j]; for(int j = 0; j < (1 << (i - 1)); j++) gg[j + (1 << i)] = fft.v[j << (K - i)] * g[j]; fft.fft(gg + (1 << i), i); for(int j = 0; j < (1 << (i + 1)); j++) gg[j] *= gg[j] * ff[j]; fft.ifft(gg, i + 1); for(int j = 1 << (i - 1); j < (1 << i); j++) g[j] = -gg[j]; for(int j = 0; j < (1 << i) - 1; j++) gg[j] = c[j + 1] * (2 * j + 2); gg[(1 << i) - 1] = 0; fft.fft(gg, i); for(int j = 0; j < (1 << i); j++) gg[j] *= ff[j]; fft.ifft(gg, i); Mint<MOD> tmp = -gg[(1 << i) - 1]; for(int j = (1 << i) - 1; j; j--) gg[j] = f[j] * j - gg[j - 1]; gg[0] = tmp; for(int j = (1 << i); j < (1 << (i + 1)); j++) gg[j] = 0; fft.fft(gg, i + 1); for(int j = 0; j < (1 << i); j++) G[j] = g[j]; fft.fft(G, i + 1); for(int j = 0; j < (1 << (i + 1)); j++) gg[j] *= G[j]; fft.ifft(gg, i + 1); for(int j = 0; j < (1 << i); j++) gg[j] = c[j + (1 << i)] - gg[j] * minv[(1 << i) + j] * im; for(int j = (1 << i); j < (1 << (i + 1)); j++) gg[j] = 0; fft.fft(gg, i + 1); for(int j = 0; j < (1 << (i + 1)); j++) ff[j] *= gg[j]; fft.ifft(ff, i + 1); for(int j = 0; j < (1 << i); j++) f[j + (1 << i)] = ff[j]; if(im.n&1) im.n += MOD; im.n /= 2; } Poly<MOD, K> r; for(int i = 0; i < (1 << K); i++) r.c[i] = f[i]; return r; } // 3 M(n) Poly<MOD, K> log() const { assert(c[0] == 1); Poly<MOD, K> g; Mint<MOD> d[1 << (K + 1)] = {}; for(int i = 0; i < (1 << K); i++) g.c[i] = c[i]; for(int i = 0; i < (1 << K); i++) d[i] = (i + 1) * c[i + 1]; g = g.inv(); fft.fft(g.c, K + 1); fft.fft(d, K + 1); Mint<MOD> im = Mint<MOD>((1+MOD)/2).pow(K + 1); for(int i = 0; i < (1 << (K + 1)); i++) g.c[i] *= d[i] * im; fft.ifft(g.c, K + 1); for(int i = (1 << K) - 1; i; i--) g.c[i] = g.c[i-1] * minv[i]; g.c[0] = 0; for(int i = 1 << K; i < (1 << (K + 1)); i++) g.c[i] = 0; return g; } // (1 + 1/2 + 1/2 + 1/2 * 2/3) M(n) = 7/3 M(n) Poly<MOD, K> quotient(const Poly<MOD, K> &Q) const { Poly<MOD, K> r; Poly<MOD, K-1> P; Mint<MOD> im = Mint<MOD>((1+MOD)/2).pow(K); for(int i = 0; i < (1 << (K - 1)); i++) P.c[i] = Q.c[i]; Poly<MOD, K-1> PP = P.inv(); fft.fft(PP.c, K); Mint<MOD> d[1 << (K + 1)] = {}; for(int i = 0; i < (1 << (K - 1)); i++) d[i] = c[i]; fft.fft(d, K); for(int i = 0; i < (1 << K); i++) d[i] *= PP.c[i] * im; fft.ifft(d, K); for(int i = (1 << (K - 1)); i < (1 << K); i++) d[i] = 0; for(int i = 0; i < (1 << (K - 1)); i++) r.c[i] = d[i]; fft.fft(d, K); fft.fft(P.c, K); for(int i = 0; i < (1 << K); i++) d[i] *= P.c[i] * im; fft.ifft(d, K); for(int i = 0; i < (1 << (K - 1)); i++) d[i] = d[i + (1 << (K - 1))], d[i + (1 << (K - 1))] = 0; fft.fft(d, K); for(int i = 0; i < (1 << K); i++) d[i] *= PP.c[i] * im; fft.ifft(d, K); for(int i = 0; i < (1 << K); i++) r.c[i] -= d[i]; return r; } }; /* template <int MOD, int K> FFT<MOD, K + 1> Poly<MOD, K>::fft; template <int MOD, int K> Minv<MOD, (1 << K) - 1> Poly<MOD, K>::minv; */ IO io; constexpr int mod = 998244353; constexpr int K = 19; void lc_conv(){ Poly<mod, K> A, B; int n = io.scan_int(); int m = io.scan_int(); for(int i=0;i<n;i++){ A.c[i] = io.scan_int(); } for(int i=0;i<m;i++){ B.c[i] = io.scan_int(); } // A *= B; Poly<mod, K>::fft.fft(A.c); Poly<mod, K>::fft.fft(B.c); const Mint<mod> t = Mint<mod>((mod+1)/2).pow(20); for(int i = 0; i < (1 << (K + 1)); i++) A.c[i] *= B.c[i] * t; Poly<mod, K>::fft.ifft(A.c); for(int i=0;i<n+m-1;i++){ io.put_int(A.c[i].n, ' '); } io.put_char('\n'); } void lc_inv(){ Poly<mod, K> A; int n = io.scan_int(); for(int i=0;i<n;i++){ A.c[i] = io.scan_int(); } Poly<mod, K> B = A.inv(); for(int i=0;i<n;i++){ io.put_int(B.c[i].n, ' '); } io.put_char('\n'); } void lc_exp(){ Poly<mod, K> A; int n = io.scan_int(); for(int i=0;i<n;i++){ A.c[i] = io.scan_int(); } Poly<mod, K> B = A.exp(); for(int i=0;i<n;i++){ io.put_int(B.c[i].n, ' '); } io.put_char('\n'); } void lc_log(){ Poly<mod, K> A; int n = io.scan_int(); for(int i=0;i<n;i++){ A.c[i] = io.scan_int(); } Poly<mod, K> B = A.log(); for(int i=0;i<n;i++){ io.put_int(B.c[i].n, ' '); } io.put_char('\n'); } void lc_sqrt(){ Poly<mod, K> A; int n = io.scan_int(); bool t = false; int d = n; Mint<mod> y, z; for(int i=0;i<n;i++){ int x = io.scan_int(); if(!t){ if(x == 0) continue; if(i & 1){ io.put_int(-1, '\n'); return; } d = i; y = Mint<mod>(x).sqrt(); if(y == mod) { io.put_int(-1, '\n'); return; } assert(y * y == x); z = Mint<mod>(x).pow(mod - 2); t = true; A.c[0] = 1; } else { A.c[i-d] = x * z; } } if(d == n){ for(int i=0;i<n;i++){ io.put_int(0, ' '); } io.put_char('\n'); return; } Poly<mod, K> B = A.sqrt(); for(int i=0;i<d/2;i++){ io.put_int(0, ' '); } for(int i=0;i<n-d/2;i++){ io.put_int((B.c[i] * y).n, ' '); } io.put_char('\n'); } void lc_part(){ Poly<mod, K> A; int n = io.scan_int(); A.c[0] = 1; for(int i=1;;i++){ int t = i*(3*i-1)/2; if(t > n) break; A.c[t] = (i&1)?mod-1:1; t += i; if(t > n) break; A.c[t] = (i&1)?mod-1:1; } Poly<mod, K> B = A.inv(); for(int i=0;i<=n;i++){ io.put_int(B.c[i].n, ' '); } io.put_char('\n'); } void lc_bernoulli(){ Poly<mod, K> A; int n = io.scan_int(); A.c[0] = 1; for(int i=1;i<=n;i++){ A.c[i] = A.c[i-1] * Poly<mod, K>::minv[i + 1]; } Poly<mod, K> B = A.inv(); Mint<mod> z = 1; for(int i=0;i<=n;i++){ io.put_int((B.c[i] * z).n, ' '); z *= i + 1; } io.put_char('\n'); } void lc_quotient(){ Poly<mod, K> A, B; int n = io.scan_int(); int m = io.scan_int(); for(int i=0;i<n;i++){ A.c[i] = io.scan_int(); } for(int i=0;i<m;i++){ B.c[i] = io.scan_int(); } Poly<mod, K> C = A.quotient(B); for(int i=0;i<n+m-1;i++){ io.put_int(C.c[i].n, ' '); } io.put_char('\n'); } int main(){ // lc_quotient(); // lc_exp(); // lc_inv(); // lc_bernoulli(); lc_part(); return 0; }