Submit Info #47790

Problem Lang User Status Time Memory
Log of Formal Power Series pypy3 rkato5680 AC 4628 ms 168.37 MiB

ケース詳細
Name Status Time Memory
example_00 AC 49 ms 29.80 MiB
max_all_zero_00 AC 4260 ms 161.71 MiB
max_random_00 AC 4608 ms 163.62 MiB
max_random_01 AC 4607 ms 164.99 MiB
max_random_02 AC 4604 ms 168.37 MiB
max_random_03 AC 4609 ms 161.93 MiB
max_random_04 AC 4628 ms 158.75 MiB
near_262144_00 AC 2920 ms 144.56 MiB
near_262144_01 AC 2931 ms 144.54 MiB
near_262144_02 AC 3632 ms 149.08 MiB
random_00 AC 3963 ms 154.14 MiB
random_01 AC 4389 ms 161.00 MiB
random_02 AC 502 ms 92.29 MiB
random_03 AC 4173 ms 157.39 MiB
random_04 AC 3856 ms 151.17 MiB
small_degree_00 AC 48 ms 29.81 MiB
small_degree_01 AC 51 ms 29.82 MiB
small_degree_02 AC 47 ms 29.88 MiB
small_degree_03 AC 50 ms 29.88 MiB
small_degree_04 AC 50 ms 29.81 MiB
small_degree_05 AC 50 ms 29.80 MiB
small_degree_06 AC 52 ms 29.81 MiB
small_degree_07 AC 54 ms 29.81 MiB
small_degree_08 AC 49 ms 29.80 MiB
small_degree_09 AC 53 ms 29.80 MiB

mod, g, ig = 998244353, 3, 332748118 W = [pow(g, (mod - 1) >> i, mod) for i in range(24)] iW = [pow(ig, (mod - 1) >> i, mod) for i in range(24)] class FPS: def __init__(self, arr=[0]): self.arr = arr self.d = len(arr) def get(self, i): return self.arr[i] __call__ = get def __neg__(self): return FPS([-self.arr[i]%mod for i in range(self.d)]) def __add__(self, other): if isinstance(other, int): return FPS([(self(i)+other)%mod for i in range(self.d)]) return FPS([(self(i)+other(i))%mod for i in range(min(self.d, other.d))]) def __sub__(self, other): if isinstance(other, int): return FPS([(self(i)-other)%mod for i in range(self.d)]) return FPS([(self(i)-other(i))%mod for i in range(min(self.d, other.d))]) def __mul__(self, other): if isinstance(other, int): return FPS([self(i)*other%mod for i in range(self.d)]) return FPS(self._convolve(self.arr, other.arr)[:max(self.d, other.d)]) def __truediv__(self, other): A,B = self.arr[:], other.arr[:] Q = [] for i in range(max(len(A)-len(B)+1, 0)): Q.append(A[i]*pow(B[0], mod-2, mod)%mod) for j in range(len(B)): A[i+j] -= Q[-1]*B[j] A[i+j] %= mod R = [] for i in range(len(A)): if A[i]: R = A[i:] break if not Q: Q = [0] if not R: R = [0] return FPS(Q+R) def __pow__(self, k): out = FPS([1]) base = self.copy() for i in range(k.bit_length()): if (k>>i)&1: out = out * base base = base*base return out def divmod(self, other): A,B = self.arr[:], other.arr[:] Q = [] for i in range(max(len(A)-len(B)+1, 0)): Q.append(A[i]*pow(B[0], mod-2, mod)%mod) for j in range(len(B)): A[i+j] -= Q[-1]*B[j] A[i+j] %= mod R = [] for i in range(len(A)): if A[i]: R = A[i:] break if not Q: Q = [0] if not R: R = [0] return FPS(Q), FPS(R) def __repr__(self): return f"FPS({self.arr}, d={self.d})" def inv(self): f = self.arr g = [pow(f[0], mod-2, mod)] while True: n = len(g) if n >= len(f): return FPS(g[:len(f)]) a = [g[i]*2%mod if i < n else 0 for i in range(n*2)] b = self._convolve(f, self._convolve(g, g))[:n*2] g = [(a[i]-b[i]) % mod for i in range(n*2)] def differentiate(self): return FPS([(self.arr[i]*i)%mod for i in range(1, self.d)]) def integrate(self, C=0): return FPS([C]+[self.arr[i]//(i+1) if self.arr[i]%(i+1)==0 else (self.arr[i] * pow(i+1, mod-2, mod))%mod for i in range(self.d)]) def log(self): return (self.differentiate() * self.inv()).integrate().modx(self.d) def exp(self): assert self.arr[0] == 0 g = FPS([0 if i else 1 for i in range(self.d)]) e = g.copy() for i in range(1,self.d.bit_length()+1): g = g * (-g.log() + self + e) g = g.modx(1<<(i+1)) g = g.modx(self.d) return g def modx(self, d0): return FPS([self.arr[i] if i < self.d else 0 for i in range(d0)]) def copy(self): return FPS(self.arr[:]) def tolist(self, copy=False): if copy: return self.arr[:] return self.arr def cumsum(self): res = [self.arr[0]] for i in range(1,self.d): res.append((res[-1]+self.arr[i])%mod) return FPS(res) def diff(self): return FPS([(self.arr[i+1]-self.arr[i])%mod for i in range(self.d-1)]) def reverse(self, inplace=False): if inplace: self.arr.reverse() return return FPS(self.arr[::-1]) def _convolve(self, a, b): def fft(f): for l in range(k, 0, -1): d = 1 << l - 1 U = [1] for i in range(d): U.append(U[-1] * W[l] % mod) for i in range(1 << k - l): for j in range(d): s = i * 2 * d + j t = s + d f[s], f[t] = (f[s] + f[t]) % mod, U[j] * (f[s] - f[t]) % mod def ifft(f): for l in range(1, k + 1): d = 1 << l - 1 U = [1] for i in range(d): U.append(U[-1] * iW[l] % mod) for i in range(1 << k - l): for j in range(d): s = i * 2 * d + j t = s + d f[s], f[t] = (f[s] + f[t] * U[j]) % mod, (f[s] - f[t] * U[j]) % mod n0 = len(a) + len(b) - 1 if len(a) < 50 or len(b) < 50: ret = [0] * n0 if len(a) > len(b): a, b = b, a for i, aa in enumerate(a): for j, bb in enumerate(b): ret[i+j] = (ret[i+j] + aa * bb) % mod return ret k = (n0).bit_length() n = 1 << k la,lb = len(a),len(b) a = [a[i] if i < la else 0 for i in range(n)] b = [b[i] if i < lb else 0 for i in range(n)] fft(a), fft(b) a = [(a[i]*b[i])%mod for i in range(n)] ifft(a) invn = pow(n, mod - 2, mod) a = [a[i]*invn %mod for i in range(n0)] return a N=int(input()) *A,=map(int,input().split()) f=FPS(A) print(*f.log().tolist())