結果

問題 No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー Kiri8128Kiri8128
提出日時 2020-05-30 03:31:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,451 bytes
コンパイル時間 241 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 79,760 KB
最終ジャッジ日時 2024-11-06 18:54:32
合計ジャッジ時間 8,194 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

def convolve(a, b):
def fft(f):
d = n // 2
v = w
while d >= 1:
u = 1
for i in range(d):
for j in range(i, n, 2*d):
f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
u = u * v % p
v = v * v % p
d //= 2
def ifft(f):
d = 1
while d < n:
v = pow(invw, n // (2 * d), p)
u = 1
for i in range(d):
for j in range(i, n, 2*d):
f[j+d] *= u
f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
u = u * v % p
d *= 2
p, g = 998244353, 3
n0, n1 = len(a), len(b)
n = 1 << (max(n0, n1) - 1).bit_length() + 1
a = a + [0] * (n-n0)
b = b + [0] * (n-n1)
w = pow(g, (p - 1) // n, p)
invw = pow(w, p-2, p)
fft(a), fft(b)
for i in range(n):
a[i] = a[i] * b[i] % p
ifft(a)
invn = pow(n, p - 2, p)
return [a[i] * invn % p for i in range(n0 + n1 - 1)]
N, Q = map(int, input().split())
P = 998244353
A = [[1] for _ in range(N)] + [[(int(a) - 1) % P, 1] for a in input().split()]
for i in range(N)[::-1]:
if i == N - 1 or i and 1 << i.bit_length() - 1 == i:
if i == N - 1:
c = 2
else:
c *= 2
A[i] = convolve(A[2*i], A[2*i+1])
for a in [int(a) for a in input().split()]:
print(A[1][a])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0