Submit Info #22675

Problem Lang User Status Time Memory
Partition Function cpp tonegawa AC 874 ms 83.80 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.67 MiB
100000_00 AC 200 ms 21.34 MiB
10000_00 AC 26 ms 3.59 MiB
1000_00 AC 0 ms 0.78 MiB
100_00 AC 1 ms 0.66 MiB
1_00 AC 1 ms 0.66 MiB
200000_00 AC 422 ms 46.89 MiB
300000_00 AC 871 ms 82.24 MiB
400000_00 AC 868 ms 83.05 MiB
500000_00 AC 874 ms 83.80 MiB
example_00 AC 1 ms 0.67 MiB

#include <iostream> #include <string> #include <vector> #include <array> #include <queue> #include <deque> #include <algorithm> #include <set> #include <map> #include <bitset> #include <cmath> #include <functional> #include <cassert> #include <iomanip> #define vll vector<ll> #define vvvl vector<vvl> #define vvl vector<vector<ll>> #define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c)) #define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c<b;c++) #define all(obj) (obj).begin(), (obj).end() typedef long long int ll; typedef long double ld; using namespace std; inline ll mpow(ll a, ll b, ll p = -1){ ll ret = 1, num = a; while(b>0){ if(b&1) ret = (ret*num)%p; num = (num*num)%p; b /= 2; } return ret; } #include <random> // modpow(x,2,mod) == aとなるxを返す // 存在しないなら-1 // mod は素数 ll modsqrt(ll a, ll mod) { a %= mod; if(a == 0) return 0LL; if(mod == 2) return 1LL; if(mpow(a, (mod - 1) / 2, mod) != 1) return -1LL; if(mod % 4 == 3) return mpow(a, mod / 4 + 1, mod); ll q = mod - 1, m = 0; while(q % 2 == 0) q >>= 1, m++; mt19937 mt; ll z; do { z = mt() % mod; } while(mpow(z, (mod - 1) / 2, mod) != mod - 1); ll c = mpow(z, q, mod); ll t = mpow(a, q, mod); ll r = mpow(a, (q + 1) >> 1, mod); for(; m > 1; --m) { ll tmp = mpow(t, 1LL << (m - 2), mod); if(tmp != 1) r = r * c % mod, t = t * (c * c % mod) % mod; c = c * c % mod; } return r; } template<ll P, ll proot> struct NTT{ ll g; vector<ll> primes; NTT(){}; ll get_mod(){return P;} void ntt(vector<ll>&f, bool inv){ int n, N = f.size(); g = mpow(proot, P/N, P); vector<ll> angles(N);angles[0] = 1; for(int i=1;i<N;i++) angles[i] = (angles[i-1] * g)%P; for(n=0;;n++) if(N == (1<<n)) break; for (int m=0;m<N;m++) { int m2 = 0; for(int i=0;i<n;i++) if(m&(1<<i)) m2 |= (1<<(n-1-i)); if(m < m2) swap(f[m], f[m2]); } for(int i=0;i<N;i++) f[i] %= P; vector<ll> power(N/2); power[0] = 1; for(int t=1;t<N;t*=2) { ll w = angles[N/(2*t)]; if(inv) w = angles[N - N/(2*t)]; for(int i=1;i<t;i++) power[i] = (power[i-1] * w)%P; for(int i=0;i<N;i+=2*t){ for (int j=0;j<t;j++){ ll x = f[i+j], y = f[i+t+j]; f[i+j] = (x + y * power[j])%P; f[i+t+j] = x - (y * power[j])%P; if(f[i+t+j]<0) f[i+t+j] += P; } } } if(inv) { ll inv = mpow(N, P-2, P); for(int i=0;i<N;i++) f[i] = (f[i]*inv)%P; } } vector<ll> conv(vector<ll> A, vector<ll> B){ assert(A.size()==B.size()); ll N = A.size(); vector<ll> C(N); ntt(A, 0); ntt(B, 0); for(int i=0;i<N;i++) C[i] = (A[i] * B[i])%P; ntt(C, 1); return C; } }; vector<ll> int32mod_conv(vector<ll> a, vector<ll> b, ll P){ if(P==998244353) return NTT<998244353, 3>().conv(a, b); NTT<167772161, 3> ntt1; NTT<469762049, 3> ntt2; NTT<1224736769, 3> ntt3; vector<ll> A = ntt1.conv(a, b); vector<ll> B = ntt2.conv(a, b); vector<ll> C = ntt3.conv(a, b); ll N = A.size(); vector<ll> ret(N); ll x = ntt1.get_mod(); ll y = ntt2.get_mod(); ll z = ntt3.get_mod(); ll ix = mpow(x, y-2, y); ll ixy = mpow((x*y)%z, z-2, z); for(int i=0;i<N;i++){ ll v = ((B[i] - A[i])*ix)%y; if(v<0) v += y; ll xxv = A[i]+x*v; v = ((C[i] - (xxv%z))*ixy)%z; if(v<0) v += z; ret[i] = ((xxv%P) + ((x*y)%P)*v)%P; } return ret; } template<ll P> struct FPS: vector<ll>{ using vector<ll>::vector; static vector<ll> itable;//integral用の逆元テーブル FPS(vll a){ ll N = 1, n = a.size(); while(N < n) N *= 2; this->resize(n); for(int i=0;i<n;i++) (*this)[i] = a[i]; } FPS operator + (const FPS& r){return FPS(*this) += r;} FPS operator - (const FPS& r){return FPS(*this) -= r;} FPS operator * (const FPS& r){return FPS(*this) *= r;} FPS operator / (const FPS& r){return FPS(*this) /= r;} FPS operator + (const ll& r){return FPS(*this) += r;} FPS operator - (const ll& r){return FPS(*this) -= r;} FPS operator * (const ll& r){return FPS(*this) *= r;} FPS operator / (const ll& r){return FPS(*this) /= r;} //多項式との演算 FPS operator += (const FPS& r){ if(r.size() > this->size()) this->resize(r.size()); for(int i=0;i<r.size();i++) { (*this)[i] += r[i]; if((*this)[i]>P) (*this)[i] -= P; } return *this; } FPS operator -= (const FPS& r){ if(r.size() > this->size()) this->resize(r.size()); for(int i=0;i<r.size();i++) { (*this)[i] -= r[i]; if((*this)[i]<0) (*this)[i] += P; } return *this; } FPS operator *= (FPS r){ ll n = max(this->size(), r.size()) * 2, N = 1; while(N < n) N*=2; this->resize(N); r.resize(N); return (*this) = (int32mod_conv(*this, r, P)); } FPS operator /= (FPS r){ return (*this) *= r.inv();} //定数との演算 FPS operator += (const ll& r){ if(this->empty()) this->resize(1); (*this)[0] += r; if((*this)[0]>P) (*this)[0] -= P; return *this; } FPS operator -= (const ll& r){ if(this->empty()) this->resize(1); (*this)[0] -= r; if((*this)[0]<0) (*this)[0] += P; return *this; } FPS operator *= (const ll& r){ if(this->empty()) this->resize(1); const ll n = this->size(); for(int i=0;i<n;i++) (*this)[i] = ((*this)[i] * r)%P; return *this; } FPS operator /= (const ll& r){ if(this->empty()) this->resize(1); ll inv = mpow(r, P-2, P); const ll n = this->size(); for(int i=0;i<n;i++) (*this)[i] = ((*this)[i] * inv)%P; return *this; } FPS operator>>(int sz) const { if(this->size() <= sz) return {}; FPS ret = *this; ret.erase(ret.begin(), ret.begin() + sz); return ret; } FPS operator<<(int sz) const { FPS ret = *this; ret.insert(ret.begin(), sz, 0); return ret; } FPS prefix(int deg){ return FPS(this->begin(), this->begin() + min((int)this->size(), deg)); } FPS inv(int deg=-1){ assert((*this)[0]!=0); const int n = this->size(); if(deg==-1) deg = n; FPS ret({mpow((*this)[0], P-2, P)}); for(int i=1;i<deg;i<<=1) ret = (ret + ret - ret * ret * prefix(i << 1)).prefix(i << 1); return ret.prefix(deg); } FPS integral(){ const int n = (int) this->size(); FPS ret(n+1); ret[0] = 0; ll inv[n+2]; inv[0] = inv[1] = 1; for(int i=0;i<n;i++) { ret[i+1] = ((*this)[i] * inv[i+1])%P; inv[i+2] = ((-(P/(i+2))*inv[P%(i+2)])%P+P)%P; } return ret; } FPS diff(){ const int n = (int) this->size(); FPS ret(max(0, n-1)); for(int i=1;i<n;i++) ret[i-1] = ((*this)[i] * i)%P; return ret; } FPS log(int deg=-1){ assert((*this)[0] == 1); const int n = (int) this->size(); if(deg==-1) deg = n; return (this->diff() * this->inv(deg)).prefix(deg-1).integral(); } FPS exp(int deg=-1){ assert((*this)[0]==0); const int n = this->size(); if(deg==-1) deg = n; FPS ret(vll{1}); for(int i=1;i<deg;i<<=1) { ret = (ret * (prefix(i << 1) + 1LL - ret.log(i << 1))).prefix(i << 1); } return ret.prefix(deg); } void print(FPS a){ ll n = a.size(); for(int i=0;i<n-1;i++) printf("%lld ", a[i]); printf("%lld\n", a[n-1]); } //初めて0以外が現れるのが奇数次数or初めに現れる数が平方根でない場合不可能(size0のFPSを返す) FPS sqrt(int deg=-1){ const int n = this->size(); if(deg==-1) deg = n; if((*this)[0]==0){ for(int i=1;i<n;i++) { if((*this)[i]!=0){ if(i&1){ std::cout << -1 << '\n'; exit(0); } if(deg-i/2<=0) break; FPS tmp = (*this >> i).sqrt(deg - i/2); if(tmp.size()==0) return {}; FPS ret = tmp << (i/2); if(ret.size()<deg) ret.resize(deg, 0); return ret; } } return FPS(deg, 0); } ll x = modsqrt((*this)[0], P); if(x==-1) return {}; FPS ret({x}); ll inv2 = mpow(2, P-2, P); for(int i=1;i<deg;i<<=1) ret = (ret + this->prefix(i << 1) * ret.inv(i << 1)) * inv2; return ret.prefix(deg); } FPS pow(ll k, int deg=-1) const{ const int n = (int) this->size(); if(deg==-1) deg = n;//桁数に注意 for(ll i=0;i<n;i++) { if((*this)[i] != 0) { ll rev = mpow((*this)[i], P-2, P); FPS C = (*this); C *= rev; FPS D(deg); for(ll j=i;j<n;j++) D[j - i] = C[j]; D = (D.log(deg) * k).exp(deg) * mpow((*this)[i], k, P); FPS E(deg); if(i*k>deg) return E; auto S = i * k; for(ll j=0;j+S<deg&&j<D.size();j++) E[j + S] = D[j]; return E; } } return *this; } ll Nth_element(ll N, FPS p, FPS q){ if(N<=20) return (p/q)[N]; FPS tmp(q.size(), 0); for(int i=0;i<q.size();i++) tmp[i] = (i%2?(P-q[i]):q[i]); p *= tmp; q *= tmp; FPS p2(p.size()/2); FPS q2(q.size()/2); if(N%2) for(int i=1;i<p.size();i+=2) p2[i/2] = p[i]; else for(int i=0;i<p.size();i+=2) p2[i/2] = p[i]; for(int i=0;i<q.size();i+=2) q2[i/2] = q[i]; return Nth_element(N/2, p2, q2); } }; int main(){ ll P = 998244353; ll n;scanf("%lld", &n); using fps = FPS<998244353>; fps A(n+1, 0); A[0] = 1; for(ll k=1;k<=n;k++){ ll k1 = (k*(3*k+1))/2; ll k2 = (k*(3*k-1))/2; if(k2 > n) break; if(k1 <= n) A[k1] = (A[k1] + ((k&1)?P-1:1))%P; if(k2 <= n) A[k2] = (A[k2] + ((k&1)?P-1:1))%P; } fps B = A.inv(); for(int i=0;i<=n;i++){ if(i==n) printf("%lld\n", B[i]); else printf("%lld ", B[i]); } }