結果
| 問題 | No.1145 Sums of Powers |
| ユーザー |
 Eki1009
|
| 提出日時 | 2020-12-23 02:24:27 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 14,851 bytes |
| コンパイル時間 | 2,064 ms |
| コンパイル使用メモリ | 81,440 KB |
| 実行使用メモリ | 81,704 KB |
| 最終ジャッジ日時 | 2023-10-21 14:03:12 |
| 合計ジャッジ時間 | 5,520 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge9 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 50 ms
60,104 KB |
| testcase_01 | AC | 50 ms
60,104 KB |
| testcase_02 | AC | 1,021 ms
81,704 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
ソースコード
mod = 998244353
sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497)
sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951)
import random
def cipolla(a, p):
a %= p
if p == 2:
return a
if a == 0:
return 0
k = (p - 1) // 2
if pow(a, k, p) != 1:
return -1
while True:
c = random.randint(2, p - 1)
theta = (c * c - a) % p
if theta == 0:
return c
if pow(theta, k, p) == p - 1:
break
k += 1
f0, f1 = c, 1
g0, g1 = 1, 0
while k:
if k & 1:
g0, g1 = f0 * g0 + theta * f1 * g1, f1 * g0 + f0 * g1
f0, f1 = f0 * f0 + theta * f1 * f1, 2 * f0 * f1
f0 %= p
f1 %= p
g0 %= p
g1 %= p
k >>= 1
return g0
def inv_gcd(a, b):
a %= b
if a == 0:
return b, 0
s, t = b, a
m0, m1 = 0, 1
while t:
u = s // t
s -= t * u
m0 -= m1 * u
s, t = t, s
m0, m1 = m1, m0
if m0 < 0:
m0 += b // s
return s, m0
def inv_mod(x):
return inv_gcd(x, mod)[1]
class Binomial:
def __init__(self):
self.fac_ = [1, 1]
self.finv_ = [1, 1]
self.inv_ = [1, 1]
def extend(self):
n = len(self.fac_)
a = self.fac_[-1] * n % mod
b = (-self.inv_[mod % n]) * (mod // n) % mod
c = self.finv_[-1] * b % mod
self.fac_.append(a)
self.inv_.append(b)
self.finv_.append(c)
def fac(self, i):
while i >= len(self.fac_):
self.extend()
return self.fac_[i]
def finv(self, i):
while i >= len(self.finv_):
self.extend()
return self.finv_[i]
def inv(self, i):
while i >= len(self.inv_):
self.extend()
return self.inv_[i]
def comb(self, n, k):
if n < k or k < 0:
return 0
return self.fac(n) * self.finv(n - r) * self.finv(r) % mod
def perm(self, n, k):
if n < k or r < 0:
return 0
return self.fac(n) * self.finv(n - k) % mod
bi = Binomial()
def butterfly(A):
n = len(A)
h = (n - 1).bit_length()
for ph in range(1, h + 1):
w = 1 << (ph - 1)
p = 1 << (h - ph)
now = 1
for s in range(w):
offset = s << (h - ph + 1)
for i in range(p):
l = A[i + offset]
r = A[i + offset + p] * now
A[i + offset] = (l + r) % mod
A[i + offset + p] = (l - r) % mod
now *= sum_e[(~s & -~s).bit_length() - 1]
now %= mod
def butterfly_inv(A):
n = len(A)
h = (n - 1).bit_length()
for ph in range(h, 0, -1):
w = 1 << (ph - 1)
p = 1 << (h - ph)
inow = 1
for s in range(w):
offset = s << (h - ph + 1)
for i in range(p):
l = A[i + offset]
r = A[i + offset + p]
A[i + offset] = (l + r) % mod
A[i + offset + p] = (mod + l - r) * inow % mod
inow *= sum_ie[(~s & -~s).bit_length() - 1]
inow %= mod
def convolution(_A, _B):
A = _A.copy()
B = _B.copy()
n = len(A)
m = len(B)
if not n or not m:
return []
if min(n, m) <= 60:
if n < m:
n, m = m, n
A, B = B, A
res = [0] * (n + m - 1)
for i in range(n):
for j in range(m):
res[i + j] += A[i] * B[j]
res[i + j] %= mod
return res
z = 1 << (n + m - 2).bit_length()
A += [0] * (z - n)
B += [0] * (z - m)
butterfly(A)
butterfly(B)
for i in range(z):
A[i] *= B[i]
A[i] %= mod
butterfly_inv(A)
A = A[:n + m - 1]
iz = inv_mod(z)
for i in range(n + m - 1):
A[i] *= iz
A[i] %= mod
return A
def autocorrelation(_A):
A = _A.copy()
n = len(A)
if not n:
return []
if n <= 60:
res = [0] * (n + n - 1)
for i in range(n):
for j in range(n):
res[i + j] += A[i] * A[j]
res[i + j] %= mod
return res
z = 1 << (n + n - 2).bit_length()
A += [0] * (z - n)
butterfly(A)
for i in range(z):
A[i] *= A[i]
A[i] %= mod
butterfly_inv(A)
A = A[:n + n - 1]
iz = inv_mod(z)
for i in range(n + n - 1):
A[i] *= iz
A[i] %= mod
return A
class formal_power_series:
def __init__(self, poly=[]):
self.poly = [p % mod for p in poly]
def __getitem__(self, key):
if isinstance(key, slice):
res = self.poly[key]
return formal_power_series(res)
else:
if key < 0:
raise IndexError("list index out of range")
if key >= len(self.poly):
return 0
else:
return self.poly[key]
def __setitem__(self, key, value):
if key < 0:
raise IndexError("list index out of range")
if key >= len(self.poly):
self.poly += [0] * (key - len(self.poly) + 1)
self.poly[key] = value % mod
def __len__(self):
return len(self.poly)
def times(self, n):
n %= mod
res = [p * n for p in self.poly]
return formal_power_series(res)
def __pos__(self):
return self
def __neg__(self):
return self.times(-1)
def __add__(self, other):
if other.__class__ == formal_power_series:
s = len(self)
t = len(other)
n = min(s, t)
res = [self.poly[i] + other.poly[i] for i in range(n)]
if s >= t:
res += self.poly[t:]
else:
res += other.poly[s:]
return formal_power_series(res)
else:
self.poly[0] += other
self.poly[0] %= mod
return self
def __radd__(self, other):
return self + other
def __sub__(self, other):
return self + (-other)
def __rsub__(self, other):
return (-self) + other
def __mul__(self, other):
if other.__class__ == formal_power_series:
res = convolution(self.poly, other.poly)
return formal_power_series(res)
else:
return self.times(other)
def __rmul__(self, other):
return self.times(other)
def __lshift__(self, other):
return formal_power_series(([0] * other) + self.poly)
def __rshift__(self, other):
return self[other:]
def square(self):
res = autocorrelation(self.poly)
return formal_power_series(res)
def inv(self, deg=-1):
assert self.poly[0]
if deg == -1:
deg = len(self) - 1
r = inv_mod(self.poly[0])
m = 1
T = [0] * (deg + 1)
T[0] = r
res = formal_power_series(T)
t = 748683265
iz = 1
while m <= deg:
F = [0] * (2 * m)
G = [0] * (2 * m)
for j in range(min(len(self), 2 * m)):
F[j] = self.poly[j]
for j in range(m):
G[j] = res[j]
butterfly(F)
butterfly(G)
for j in range(2 * m):
F[j] *= G[j]
F[j] %= mod
butterfly_inv(F)
for j in range(m):
F[j] = 0
butterfly(F)
for j in range(2 * m):
F[j] *= G[j]
F[j] %= mod
butterfly_inv(F)
iz *= t
iz %= mod
for j in range(m, min(2 * m, deg + 1)):
res[j] = -F[j]*iz
m <<= 1
return res
#P/Q
def __truediv__(self, other):
if other.__class__ == formal_power_series:
return (self * other.inv())
else:
return self * inv_mod(other)
def __rtruediv__(self, other):
return other * self.inv()
#P,Qを多項式として見たときのPをQで割った商を求める
def __floordiv__(self, other):
if other.__class__ == formal_power_series:
if len(self) < len(other):
return formal_power_series()
else:
m = len(self) - len(other) + 1
res = (self[-1:-m-1:-1] * other[::-1].inv(m))[m-1::-1]
return res
else:
return self * inv_mod(other)
def __rfloordiv__(self, other):
return other * self.inv()
def __mod__(self, other):
if len(self) < len(other):
return self[:]
else:
res = self[:len(other) - 1] - ((self // other) * other)[:len(other) - 1]
return res
def differentiate(self):
res = [k * p for k, p in enumerate(self.poly[1:], 1)]
return formal_power_series(res)
def integrate(self):
res = [0] + [bi.inv(k) * p for k, p in enumerate(self.poly, 1)]
return formal_power_series(res)
def log(self, deg=-1):
if deg == -1:
deg = len(self) - 1
return (self.differentiate() * self.inv(deg))[:deg].integrate()
def exp(self, deg=-1):
if deg == -1:
deg = len(self) - 1
res = formal_power_series([1])
G = formal_power_series([1])
df = self.differentiate()
m = 1
while m <= deg:
G = G * 2 - (res * G.square())[:m]
m <<= 1
dft = df[:m]
W = dft + (G * (res.differentiate() - (res * dft)[:m]))[:m]
res += (res * (self[:m] - W.integrate()[:m]))[:m]
return res[:deg + 1]
def __pow__(self, n, deg=-1):
if deg == -1:
deg = len(self) - 1
m = abs(n)
for d, p in enumerate(self.poly):
if p:
break
else:
return formal_power_series()
if d * m >= len(self):
return formal_power_series()
G = self[d:]
G = ((G * inv_mod(p)).log() * m).exp() * pow(p, m, mod)
res = formal_power_series([0] * (d * m) + G.poly)
if n >= 0:
return res[:deg + 1]
else:
return res.inv()[:deg + 1]
def sqrt(self, deg=-1):
if deg == -1:
deg = len(self) - 1
if len(self) == 0:
return formal_power_series()
if self.poly[0] == 0:
for d in range(1, len(self)):
if self.poly[d]:
if d & 1:
return -1
if deg < d // 2:
break
res = self[d:].sqrt(deg - d // 2)
if res == -1:
return -1
res = res << (d // 2)
return res
return formal_power_series()
sqr = cipolla(self.poly[0], mod)
if sqr == -1:
return -1
T = [0] * (deg + 1)
T[0] = sqr
res = formal_power_series(T)
two_inv = (mod + 1) // 2
m = 1
while m <= deg:
m <<= 1
k = min(m, deg + 1)
res = res + (self[:k] * res.inv(k -1))[:k]
res = res * two_inv
return res
#各p_i(0<=i<m)についてf(p_i)を求める
def multipoint_evaluation(self, P):
m = len(P)
size = 1 << (m - 1).bit_length()
G = [formal_power_series([1]) for _ in range(2 * size)]
for i in range(m):
G[size + i] = formal_power_series([-P[i], 1])
for i in range(size - 1, 0, -1):
G[i] = G[2 * i] * G[2 * i + 1]
G[1] = self % G[1]
for i in range(2, size + m):
G[i] = G[i >> 1] % G[i]
res = [G[i][0] for i in range(size, size + m)]
return res
def taylor_shift(self, a):
n = len(self)
res = self[:]
for i in range(n):
res[i] *= bi.fac(i)
res = res[::-1]
G = formal_power_series([0] * n)
G[0] = 1
for i in range(1, n):
G[i] = G[i - 1] * a * bi.inv(i)
res = (res * G)[:n]
res = res[::-1]
for i in range(n):
res[i] *= bi.finv(i)
return res
#[x^n]P/Qを求める
def poly_coef(Q, P, n):
while n:
R = [0] * len(Q.poly)
for i, q in enumerate(Q.poly):
if i & 1:
R[i] = -q
else:
R[i] = q
R = formal_power_series(R)
P = P * R
Q = Q * R
if n & 1:
P = P[1::2]
else:
P = P[::2]
Q = Q[::2]
n >>= 1
return P[0]
def subset_sum(A, limit):
C = [0] * (limit + 1)
for a in A:
C[a] += 1
res = formal_power_series([0] * (limit + 1))
for i in range(1, limit + 1):
for k in range(1, limit // i + 1):
j = i * k
res[j] += ((k & 1) * 2 - 1) * C[i] * bi.inv(k)
return res.exp(limit).poly
def partition_function(n):
res = formal_power_series([0] * (n + 1))
res[0] = 1
for k in range(1, n+1):
k1 = k * (3 * k + 1 )// 2
k2 = k * (3 * k - 1) // 2
if k2 > n:
break
if k1 <= n:
res[k1] += 1 - (k & 1) * 2
if k2 <= n:
res[k2] += 1 - (k & 1) * 2
return res.inv().poly
def bernoulli_number(n):
n += 1
Q = formal_power_series([bi.finv(i + 1) for i in range(n)]).inv(n - 1)
res = [v * bi.fac(i) % mod for i, v in enumerate(Q.poly)]
return res
def stirling_first(n):
if n <= 0:
return formal_power_series([1])
lg = (n - 1).bit_length()
res = formal_power_series([0, 1])
for i in range(lg - 1, -1, -1):
k = n >> i
F *= F.taylor_shift(k >> 1)
def stirling_second(n):
F = formal_power_series([0] * (n + 1))
G = formal_power_series([0] * (n + 1))
for i in range(n + 1):
F[i] = pow(i, n, mod) * bi.finv(i)
G[i] = (1 - (i & 1) * 2) * bi.finv(i)
return (F * G)[:n + 1].poly
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = tuple(map(int, input().split()))
F = formal_power_series([0]*(m+1))
for a in A:
T = formal_power_series([1, -a]).log(m)
F += T
L = []
for k in range(1, m+1):
L.append(-F[k] * k % mod)
print(*L)