結果
| 問題 | No.2966 Simple Plus Minus Problem |
| ユーザー |
 ねしん
|
| 提出日時 | 2024-10-21 22:10:56 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,169 ms / 2,567 ms |
| コード長 | 7,823 bytes |
| コンパイル時間 | 367 ms |
| コンパイル使用メモリ | 82,364 KB |
| 実行使用メモリ | 145,132 KB |
| 最終ジャッジ日時 | 2024-10-30 08:23:50 |
| 合計ジャッジ時間 | 30,127 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 39 ms
53,736 KB |
| testcase_01 | AC | 41 ms
53,420 KB |
| testcase_02 | AC | 39 ms
54,652 KB |
| testcase_03 | AC | 670 ms
111,852 KB |
| testcase_04 | AC | 1,148 ms
130,768 KB |
| testcase_05 | AC | 39 ms
55,296 KB |
| testcase_06 | AC | 53 ms
65,660 KB |
| testcase_07 | AC | 127 ms
78,264 KB |
| testcase_08 | AC | 114 ms
78,024 KB |
| testcase_09 | AC | 130 ms
78,228 KB |
| testcase_10 | AC | 74 ms
74,784 KB |
| testcase_11 | AC | 127 ms
78,060 KB |
| testcase_12 | AC | 76 ms
74,600 KB |
| testcase_13 | AC | 129 ms
78,292 KB |
| testcase_14 | AC | 75 ms
74,728 KB |
| testcase_15 | AC | 105 ms
77,300 KB |
| testcase_16 | AC | 44 ms
56,124 KB |
| testcase_17 | AC | 131 ms
78,436 KB |
| testcase_18 | AC | 76 ms
74,708 KB |
| testcase_19 | AC | 115 ms
77,920 KB |
| testcase_20 | AC | 127 ms
78,020 KB |
| testcase_21 | AC | 101 ms
77,432 KB |
| testcase_22 | AC | 55 ms
64,972 KB |
| testcase_23 | AC | 112 ms
77,572 KB |
| testcase_24 | AC | 142 ms
78,684 KB |
| testcase_25 | AC | 142 ms
78,452 KB |
| testcase_26 | AC | 114 ms
77,960 KB |
| testcase_27 | AC | 140 ms
78,580 KB |
| testcase_28 | AC | 121 ms
77,996 KB |
| testcase_29 | AC | 142 ms
78,472 KB |
| testcase_30 | AC | 103 ms
77,164 KB |
| testcase_31 | AC | 128 ms
78,268 KB |
| testcase_32 | AC | 39 ms
54,060 KB |
| testcase_33 | AC | 39 ms
53,928 KB |
| testcase_34 | AC | 639 ms
105,320 KB |
| testcase_35 | AC | 1,141 ms
129,908 KB |
| testcase_36 | AC | 652 ms
109,336 KB |
| testcase_37 | AC | 644 ms
107,176 KB |
| testcase_38 | AC | 690 ms
115,080 KB |
| testcase_39 | AC | 711 ms
115,984 KB |
| testcase_40 | AC | 656 ms
108,936 KB |
| testcase_41 | AC | 1,157 ms
142,460 KB |
| testcase_42 | AC | 724 ms
115,896 KB |
| testcase_43 | AC | 1,167 ms
140,016 KB |
| testcase_44 | AC | 733 ms
118,384 KB |
| testcase_45 | AC | 1,169 ms
145,028 KB |
| testcase_46 | AC | 1,155 ms
144,312 KB |
| testcase_47 | AC | 692 ms
115,540 KB |
| testcase_48 | AC | 1,163 ms
130,320 KB |
| testcase_49 | AC | 731 ms
118,228 KB |
| testcase_50 | AC | 643 ms
109,488 KB |
| testcase_51 | AC | 675 ms
112,368 KB |
| testcase_52 | AC | 1,164 ms
144,204 KB |
| testcase_53 | AC | 1,162 ms
144,700 KB |
| testcase_54 | AC | 1,161 ms
145,076 KB |
| testcase_55 | AC | 1,164 ms
145,132 KB |
| testcase_56 | AC | 1,164 ms
145,056 KB |
ソースコード
#https://atcoder.jp/contests/practice2/submissions/48921277からお借りしております。
class FFT():
def primitive_root_constexpr(self, m):
if m == 2: return 1
if m == 167772161: return 3
if m == 469762049: return 3
if m == 754974721: return 11
if m == 998244353: return 3
divs = [0] * 20
divs[0] = 2
cnt = 1
x = (m - 1) // 2
while (x % 2 == 0): x //= 2
i = 3
while (i * i <= x):
if (x % i == 0):
divs[cnt] = i
cnt += 1
while (x % i == 0):
x //= i
i += 2
if x > 1:
divs[cnt] = x
cnt += 1
g = 2
while (1):
ok = True
for i in range(cnt):
if pow(g, (m - 1) // divs[i], m) == 1:
ok = False
break
if ok:
return g
g += 1
def bsf(self, x):
res = 0
while (x % 2 == 0):
res += 1
x //= 2
return res
rank2 = 0
root = []
iroot = []
rate2 = []
irate2 = []
rate3 = []
irate3 = []
def __init__(self, MOD):
self.mod = MOD
self.g = self.primitive_root_constexpr(self.mod)
self.rank2 = self.bsf(self.mod - 1)
self.root = [0 for i in range(self.rank2 + 1)]
self.iroot = [0 for i in range(self.rank2 + 1)]
self.rate2 = [0 for i in range(self.rank2)]
self.irate2 = [0 for i in range(self.rank2)]
self.rate3 = [0 for i in range(self.rank2 - 1)]
self.irate3 = [0 for i in range(self.rank2 - 1)]
self.root[self.rank2] = pow(self.g, (self.mod - 1) >> self.rank2,
self.mod)
self.iroot[self.rank2] = pow(self.root[self.rank2], self.mod - 2,
self.mod)
for i in range(self.rank2 - 1, -1, -1):
self.root[i] = (self.root[i + 1] ** 2) % self.mod
self.iroot[i] = (self.iroot[i + 1] ** 2) % self.mod
prod = 1;
iprod = 1
for i in range(self.rank2 - 1):
self.rate2[i] = (self.root[i + 2] * prod) % self.mod
self.irate2[i] = (self.iroot[i + 2] * iprod) % self.mod
prod = (prod * self.iroot[i + 2]) % self.mod
iprod = (iprod * self.root[i + 2]) % self.mod
prod = 1;
iprod = 1
for i in range(self.rank2 - 2):
self.rate3[i] = (self.root[i + 3] * prod) % self.mod
self.irate3[i] = (self.iroot[i + 3] * iprod) % self.mod
prod = (prod * self.iroot[i + 3]) % self.mod
iprod = (iprod * self.root[i + 3]) % self.mod
def butterfly(self, a):
n = len(a)
h = (n - 1).bit_length()
LEN = 0
while (LEN < h):
if (h - LEN == 1):
p = 1 << (h - LEN - 1)
rot = 1
for s in range(1 << LEN):
offset = s << (h - LEN)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p] * rot
a[i + offset] = (l + r) % self.mod
a[i + offset + p] = (l - r) % self.mod
rot *= self.rate2[(~s & -~s).bit_length() - 1]
rot %= self.mod
LEN += 1
else:
p = 1 << (h - LEN - 2)
rot = 1
imag = self.root[2]
for s in range(1 << LEN):
rot2 = (rot * rot) % self.mod
rot3 = (rot2 * rot) % self.mod
offset = s << (h - LEN)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p] * rot
a2 = a[i + offset + 2 * p] * rot2
a3 = a[i + offset + 3 * p] * rot3
a1na3imag = (a1 - a3) % self.mod * imag
a[i + offset] = (a0 + a2 + a1 + a3) % self.mod
a[i + offset + p] = (a0 + a2 - a1 - a3) % self.mod
a[i + offset + 2 * p] = (
a0 - a2 + a1na3imag) % self.mod
a[i + offset + 3 * p] = (
a0 - a2 - a1na3imag) % self.mod
rot *= self.rate3[(~s & -~s).bit_length() - 1]
rot %= self.mod
LEN += 2
def butterfly_inv(self, a):
n = len(a)
h = (n - 1).bit_length()
LEN = h
while (LEN):
if (LEN == 1):
p = 1 << (h - LEN)
irot = 1
for s in range(1 << (LEN - 1)):
offset = s << (h - LEN + 1)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p]
a[i + offset] = (l + r) % self.mod
a[i + offset + p] = (l - r) * irot % self.mod
irot *= self.irate2[(~s & -~s).bit_length() - 1]
irot %= self.mod
LEN -= 1
else:
p = 1 << (h - LEN)
irot = 1
iimag = self.iroot[2]
for s in range(1 << (LEN - 2)):
irot2 = (irot * irot) % self.mod
irot3 = (irot * irot2) % self.mod
offset = s << (h - LEN + 2)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p]
a2 = a[i + offset + 2 * p]
a3 = a[i + offset + 3 * p]
a2na3iimag = (a2 - a3) * iimag % self.mod
a[i + offset] = (a0 + a1 + a2 + a3) % self.mod
a[i + offset + p] = (
a0 - a1 + a2na3iimag) * irot % self.mod
a[i + offset + 2 * p] = (
a0 + a1 - a2 - a3) * irot2 % self.mod
a[i + offset + 3 * p] = (
a0 - a1 - a2na3iimag) * irot3 % self.mod
irot *= self.irate3[(~s & -~s).bit_length() - 1]
irot %= self.mod
LEN -= 2
def convolution(self, a, b):
n = len(a);
m = len(b)
if not (a) or not (b):
return []
if min(n, m) <= 40:
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] %= self.mod
return res
z = 1 << ((n + m - 2).bit_length())
a = a + [0] * (z - n)
b = b + [0] * (z - m)
self.butterfly(a)
self.butterfly(b)
c = [(a[i] * b[i]) % self.mod for i in range(z)]
self.butterfly_inv(c)
iz = pow(z, self.mod - 2, self.mod)
for i in range(n + m - 1):
c[i] = (c[i] * iz) % self.mod
return c[:n + m - 1]
N, K = map(int, input().split())
MOD=998244353
M=K//2
A = list(map(int,input().split()))
B = [1]
for i in range(N-1):
B.append((B[-1]*pow(i+1,MOD-2,MOD)*(M+i))%MOD)
C=[]
D=[]
for i in range(N):
if i%2==0:
C.append(A[i])
else:
D.append(A[i])
CONV=FFT(MOD)
CONV2=FFT(MOD)
L=CONV.convolution(C, B)
Q=CONV2.convolution(D, B)
ans=[]
for i in range(N):
if i%2==0:
ans.append(L[i//2])
else:
ans.append(Q[i//2])
if K%2==1:
for i in range(1,N):
ans[i]=(ans[i-1]+ans[i]*(-1)**(i%2))%MOD
print(*ans)