結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
57,856 KB
testcase_01 AC 41 ms
51,968 KB
testcase_02 AC 41 ms
52,096 KB
testcase_03 AC 219 ms
78,580 KB
testcase_04 AC 238 ms
79,272 KB
testcase_05 AC 251 ms
79,356 KB
testcase_06 AC 206 ms
78,956 KB
testcase_07 AC 194 ms
79,048 KB
testcase_08 AC 244 ms
79,760 KB
testcase_09 AC 254 ms
78,756 KB
testcase_10 AC 184 ms
78,392 KB
testcase_11 AC 186 ms
78,456 KB
testcase_12 AC 174 ms
78,484 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