結果

問題 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
コンパイル時間 203 ms
コンパイル使用メモリ 82,944 KB
実行使用メモリ 79,872 KB
最終ジャッジ日時 2024-04-24 11:12:00
合計ジャッジ時間 7,834 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,864 KB
testcase_01 AC 36 ms
52,480 KB
testcase_02 AC 36 ms
52,224 KB
testcase_03 AC 217 ms
79,088 KB
testcase_04 AC 209 ms
79,788 KB
testcase_05 AC 215 ms
79,740 KB
testcase_06 AC 185 ms
79,460 KB
testcase_07 AC 169 ms
79,460 KB
testcase_08 AC 214 ms
79,872 KB
testcase_09 AC 224 ms
79,400 KB
testcase_10 AC 161 ms
79,032 KB
testcase_11 AC 166 ms
78,436 KB
testcase_12 AC 157 ms
78,604 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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])
0