Submit Info #415

Problem Lang User Status Time Memory
Partition Function cpp ryuhei AC 221 ms 22.05 MiB

ケース詳細
Name Status Time Memory
0_00 AC 0 ms 0.72 MiB
100000_00 AC 53 ms 5.42 MiB
10000_00 AC 6 ms 1.05 MiB
1000_00 AC 2 ms 0.67 MiB
100_00 AC 0 ms 0.67 MiB
1_00 AC 1 ms 0.67 MiB
200000_00 AC 111 ms 10.34 MiB
300000_00 AC 218 ms 18.24 MiB
400000_00 AC 219 ms 20.17 MiB
500000_00 AC 221 ms 22.05 MiB
example_00 AC 1 ms 0.71 MiB

#include <unistd.h> #include <stdlib.h> char ibuf[50]; char *ibufe = ibuf-1; void readall(){ int k, t = 0; while((k=read(STDIN_FILENO, ibuf+t, sizeof(ibuf)-t))>0) t += k; } char buf[5000000]; char *bufe = buf; void writeall(){ int k, t = 0; while((k=write(STDOUT_FILENO, buf+t, bufe-buf-t))>0) t += k; } int read_uint(){ int x=0; while(*(++ibufe) <'0'); do { x *= 10; x += *ibufe-'0'; } while(*(++ibufe) >='0'); return x; } int read_int(){ int x=0, y=0; while(*(++ibufe) <'-'); if(*ibufe == '-'){ y = 1; ibufe++; } do { x *= 10; x += *ibufe-'0'; } while(*(++ibufe) >='0'); if(y) x = -x; return x; } void write_uintln(unsigned int x){ int i; static char tmp[13]; /* if(bufe-buf < 20){ writeall(); bufe = buf; } */ if(x==0){ *bufe++ = '0'; *bufe++ = '\n'; return; } for(i=0; x; i++){ tmp[i] = '0' + x % 10; x /= 10; } for(i--; i >= 0; i--){ *bufe++ = tmp[i]; } *bufe++ = '\n'; } //#define K 27 //#define M (1U<<K) typedef unsigned Zp; //const Zp mod = 469762049; //const Zp mod = 2281701377; //const Zp mod = 2013265921; //const Zp root = 100680575; //const Zp root = 3; //const Zp mod = 2013265921; //const Zp root = 31; //const Zp mod = 3221225473; //const Zp root = 5; const Zp mod = 998244353; const Zp root = 3; //Zp Q[M<<1]; //Zp w[M>>1]; //Zp y[M>>1]; //Zp v[M>>1]; Zp *Q, *w, *y; Zp add(Zp lhs, Zp rhs){ /* unsigned long long r = lhs + rhs; if(r >= mod) return r - mod; else return r; */ // if(rhs == 0) return lhs; rhs = mod-rhs; if(lhs >= rhs) return lhs - rhs; else return mod + lhs - rhs; } Zp sub(Zp lhs, Zp rhs){ if(lhs >= rhs) return lhs - rhs; else return mod + lhs - rhs; } Zp mul(Zp lhs, Zp rhs){ return ((unsigned long long) lhs * rhs) % mod; } Zp powr(Zp x, Zp n){ Zp r = 1; for(; n; n>>=1){ if(n&1) r = mul(r, x); x = mul(x, x); } return r; } Zp inv(Zp x){ return powr(x, mod-2); } //Zp tmp[M]; void fft(Zp *A, int k){ int i, j, jh, je; const int m = 1 << k; int u = 1; int v = m/2; for(i=k;i>0;i--){ for(jh=0;jh<u;jh++){ Zp wj = w[jh]; for(j = jh << i, je = j+v;j<je; j++){ Zp Ajv = mul(wj, A[j+v]); A[j+v] = sub(A[j], Ajv); A[j] = add(A[j], Ajv); } } u <<= 1; v >>= 1; } } /* void fft(Zp *A, int k){ int i, j; const int m = 1 << k; Zp *P, *Q, *R; P = A; Q = tmp; for(i=0;i<k;i++){ for(j=0;j<m/2;j++){ Zp Ajv = mul(w[j&((1<<i)-1)], P[j+m/2]); Q[2*j] = add(P[j], Ajv); Q[2*j+1] = sub(P[j], Ajv); } R = P; P = Q; Q = R; } if(k&1){ for(i=0;i<m;i++) A[i] = tmp[i]; } } */ void ifft(Zp *A, int k){ int i, j, jh, je; const int m = 1 << k; int u = m/2; int v = 1; for(i=1;i<=k;i++){ for(jh=0;jh<u;jh++){ Zp wj = y[jh]; for(j = jh << i, je = j+v;j<je; j++){ Zp Ajv = sub(A[j], A[j+v]); A[j] = add(A[j], A[j+v]); A[j+v] = mul(wj, Ajv); } } u >>= 1; v <<= 1; } } void genwy(int i, int b, Zp z, Zp x){ if(b == 0) { w[i] = z; y[i] = x; } else { genwy(i, b>>1, z, x); genwy(i|b, b>>1, mul(z, w[b]), mul(x, y[b])); } } int main(){ int i, j; int n; readall(); n = read_uint(); if(n == 0){ write_uintln(1); writeall(); return 0; } int size = 33-__builtin_clz(n); Q = (Zp*) calloc(1<<(size+1), sizeof(*Q)); w = (Zp*) malloc(sizeof(*w)<<(size-1)); y = (Zp*) malloc(sizeof(*y)<<(size-1)); if(Q==NULL||w==NULL||y==NULL) return 1; Q[0] = 1; for(i=1;;i++){ int t = i*(3*i-1)/2; if(t > n) break; Q[t] = (i&1)?mod-1:1; t += i; if(t > n) break; Q[t] = (i&1)?mod-1:1; } Zp z=powr(root,(mod-1)>>size); Zp x=inv(z); for(j=(1<<(size-2)); j; j>>=1){ w[j] = z; z = mul(z, z); y[j] = x; x = mul(x, x); } genwy(0, 1<<(size-2), 1, 1); // int size = 33-__builtin_clz(k); //write_uintln(size); fft(Q, size); /* Zp wi = 1; for(i=0;i<M/2;i++){ v[i] = wi; wi = mul(wi, root); } */ Zp normal = 0; Zp *QQ = Q; Zp im = inv((1<<(size-1))%mod); for(;size>1;){ Zp *QQQ = QQ + (1<<size); for(i=0;i<(1<<(size-1));i++) QQQ[i] = mul(QQ[2*i], QQ[2*i+1]); QQ = QQQ; size--; ifft(QQ, size); for(i=0;i<(1<<size);i++){ if(i<(1<<(size-1))) QQ[i] = mul(QQ[i], im); else QQ[i] = 0; } im = add(im, im); fft(QQ, size); } while(QQ > Q){ Zp *QQQ = QQ - (1<<(size+1)); for(i=0;i<(1<<size);i++){ Zp tmp0 = mul(QQQ[2*i], QQ[i]); Zp tmp1 = mul(QQQ[2*i+1], QQ[i]); QQQ[2*i] = tmp1; QQQ[2*i+1] = tmp0; } size++; QQ = QQQ; ifft(QQ, size); for(i=(1<<(size-1));i<(1<<size);i++) QQ[i] = 0; fft(QQ, size); normal += size; } ifft(Q, size); normal += size; Zp iim = inv(powr(2, normal)); for(i=0;i<=n;i++) write_uintln(mul(Q[i], iim)); writeall(); return 0; }