Submit Info #8608

Problem Lang User Status Time Memory
Partition Function java 37zigen AC 1111 ms 115.51 MiB

ケース詳細
Name Status Time Memory
0_00 AC 426 ms 36.24 MiB
100000_00 AC 700 ms 60.34 MiB
10000_00 AC 507 ms 39.32 MiB
1000_00 AC 461 ms 36.59 MiB
100_00 AC 439 ms 36.27 MiB
1_00 AC 434 ms 36.23 MiB
200000_00 AC 838 ms 84.41 MiB
300000_00 AC 1100 ms 114.57 MiB
400000_00 AC 1111 ms 113.33 MiB
500000_00 AC 1107 ms 115.51 MiB
example_00 AC 422 ms 36.28 MiB

import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; public class Main{ public static void main(String[] args) { new Main().run(); } final long p=998244353; final long g=3; long pow(long a,long n) { return n!=0?(pow(a*a%p,n/2)*(n%2==1?a:1))%p:1; } long inv(long a) { return pow(a,p-2); } long ADD(long a,long b) { return a+b>=p?a+b-p:a+b; } long SUB(long a,long b) { return ADD(a,p-b); } void fft(long[] a,long g) { int n=a.length; { int cur=0; for (int i=0;i<n;++i) { if (cur<i) { a[i]^=a[cur];a[cur]^=a[i];a[i]^=a[cur]; } for (int k=n/2;k>(cur^=k);k/=2) ; } } for (int s=1;s<=n/2;s*=2) { long mul=pow(g,n/(2*s)); for (int i=0;i<n;i+=2*s) { long x=1; for (int j=0;j<s;++j) { long A=a[i+j]; long B=a[i+j+s]*x%p; a[i+j]=ADD(A,B); a[i+j+s]=SUB(A,B); x=x*mul%p; } } } } long[] mul(long[] a,long[] b) { int n=1; while (n<a.length+b.length-1) n*=2; a=Arrays.copyOf(a, n); b=Arrays.copyOf(b, n); long root=pow(g,(p-1)/n); fft(a,root); fft(b,root); long in=inv(n); for (int i=0;i<n;++i) a[i]=a[i]*b[i]%p*in%p; fft(a,inv(root)); return a; } long[] inv(long[] a) { int n=a.length; long[] G= {inv(a[0])}; for (int len=1;len<n;len*=2) { long[] prd=mul(mul(G,G),Arrays.copyOf(a, 2*len)); G=Arrays.copyOf(G, 2*len); for (int i=0;i<2*len;++i) { G[i]=(2*G[i]+p-prd[i])%p; } } return G; } long[] differentiate(long[] a) { long[] ret=new long[a.length]; for (int i=0;i+1<ret.length;++i) ret[i]=(i+1)*a[i+1]%p; return ret; } long[] integrate(long[] a) { long[] ret=new long[a.length]; for (int i=0;i+1<ret.length;++i) ret[i+1]=inv(i+1)*a[i]%p; return ret; } long[] log(long[] a) { return integrate(mul(differentiate(a),inv(a))); } long[] exp(long[] a) { int n=a.length; long[] G= {1}; for (int len=1;len<n;len*=2) { long[] log=log(Arrays.copyOf(G, 2*len)); for (int i=0;i<Math.min(n,2*len);++i) log[i]=(p-log[i]+a[i])%p; log[0]=ADD(log[0],1); G=Arrays.copyOf(mul(G,log),2*len); } return G; } void reverse(long[] a) { int s=0,t=a.length-1; while (s<t) { a[s]^=a[t];a[t]^=a[s];a[s]^=a[t]; ++s;--t; } } long[] fac=new long[(int)1.5e6]; long[] ifac=new long[(int)1.5e6]; { fac[0]=1; for (int i=1;i<fac.length;++i) fac[i]=i*fac[i-1]%p; for (int i=0;i<ifac.length;++i) ifac[i]=inv(fac[i]); } long[] shift(long[] a_,long shift) { long[] a=Arrays.copyOf(a_, a_.length); int n=a.length; for (int i=0;i<n;++i) { a[i]=a[i]*fac[i]%p; } reverse(a); long[] b=new long[n]; long pow=1; for (int i=0;i<n;++i) { b[i]=pow%p*ifac[i]%p; pow=pow*shift%p; } a=mul(a,b); a=Arrays.copyOf(a, n); reverse(a); for (int i=0;i<n;++i) { a[i]=ifac[i]*a[i]%p; } return a; } void run() { FastScanner sc=new FastScanner(); PrintWriter pw=new PrintWriter(System.out); int N=sc.nextInt(); long[] F; { long[] denominator=new long[N+1]; denominator[0]=1; for (int i=1;i*(3*i-1)/2<=N;++i) { if (i%2==0) denominator[i*(3*i-1)/2]++; else denominator[i*(3*i-1)/2]--; } for (int i=1;i*(3*i+1)/2<=N;++i) { if (i%2==0) denominator[i*(3*i+1)/2]++; else denominator[i*(3*i+1)/2]--; } for (int i=0;i<denominator.length;++i) denominator[i]=(p+denominator[i])%p; F=inv(denominator); } for (int i=0;i<=N;++i) { pw.print(F[i]+(i==N?"\n":" ")); } pw.close(); } void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));} } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;} public boolean hasNext() { skipUnprintable(); return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { return (int)nextLong(); } }