結果
問題 | No.1068 #いろいろな色 / Red and Blue and more various colors (Hard) |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
def convolve(a, b):def fft(f):d = n // 2v = wwhile d >= 1:u = 1for 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]) % pu = u * v % pv = v * v % pd //= 2def ifft(f):d = 1while d < n:v = pow(invw, n // (2 * d), p)u = 1for i in range(d):for j in range(i, n, 2*d):f[j+d] *= uf[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % pu = u * v % pd *= 2p, g = 998244353, 3n0, n1 = len(a), len(b)n = 1 << (max(n0, n1) - 1).bit_length() + 1a = 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] % pifft(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 = 998244353A = [[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 = 2else:c *= 2A[i] = convolve(A[2*i], A[2*i+1])for a in [int(a) for a in input().split()]:print(A[1][a])