Submit Info #2381

Problem Lang User Status Time Memory
Partition Function python3 maspy AC 1435 ms 143.51 MiB

ケース詳細
Name Status Time Memory
0_00 AC 91 ms 13.88 MiB
100000_00 AC 370 ms 44.34 MiB
10000_00 AC 118 ms 17.83 MiB
1000_00 AC 97 ms 14.22 MiB
100_00 AC 97 ms 13.94 MiB
1_00 AC 96 ms 13.95 MiB
200000_00 AC 682 ms 73.48 MiB
300000_00 AC 1310 ms 123.58 MiB
400000_00 AC 1412 ms 132.81 MiB
500000_00 AC 1435 ms 143.51 MiB
example_00 AC 94 ms 13.98 MiB

import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np MOD = 998244353 def fft_convolve(f, g, MOD = MOD): """ 数列 (多項式) f, g の畳み込みの計算.上下 15 bitずつ分けて計算することで, 30 bit以下の整数,長さ 250000 程度の数列での計算が正確に行える. """ fft = np.fft.rfft; ifft = np.fft.irfft Lf = len(f); Lg = len(g); L = Lf + Lg - 1 fft_len = 1 << L.bit_length() fl = f & (1 << 15) - 1; fh = f >> 15 gl = g & (1 << 15) - 1; gh = g >> 15 conv = lambda f,g: ifft(fft(f,fft_len) * fft(g,fft_len))[:L] x = conv(fl, gl) % MOD y = conv(fl+fh, gl+gh) % MOD z = conv(fh, gh) % MOD a, b, c = map(lambda x: (x + .5).astype(np.int64), [x,y,z]) return (a + ((b - a - c) << 15) + (c << 30)) % MOD def fps_inv(F,MOD=MOD): L = len(F) i = (L-1).bit_length() N = 1 << i F = np.resize(F,N) n = 1 x = pow(int(F[0]),MOD-2,MOD) R = np.array([x],np.int64) while n < N: RF = fft_convolve(R,F[:n+n])[:n+n] RRF = fft_convolve(R,-RF)[:n+n] RRF[:n] += R+R R = RRF; R %= MOD n += n return R[:L] def partition_number(N,MOD=MOD): # 五角数定理で分母を求めてfps_inv M = int(N**.5 + 10) x = np.arange(-M,M) P = x * (3*x-1) // 2 pos = P[M&1::2]; neg = P[(M+1)&1::2] pos = pos[pos < N]; neg = neg[neg < N] f = np.zeros(N,np.int64) np.add.at(f,pos,1); np.add.at(f,neg,-1) return fps_inv(f,MOD) N = int(read()) A = partition_number(N+1) print(' '.join(A.astype(str)))