結果

問題 No.1618 Convolution?
ユーザー 👑 rin204rin204
提出日時 2022-03-21 22:41:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,714 bytes
コンパイル時間 358 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 205,412 KB
最終ジャッジ日時 2024-04-17 19:35:29
合計ジャッジ時間 4,867 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
58,240 KB
testcase_01 AC 38 ms
53,376 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def f(A, B):
    def convolve(a, b, MOD=998244353):
        def primitive_root_constexpr():
            if MOD == 998244353:
                return 3
            elif MOD == 2:
                return 1
            elif MOD == 200003:
                return 2
            elif MOD == 167772161:
                return 3
            elif MOD == 469762049:
                return 3
            elif MOD == 754974721:
                return 11
            divs = [0] * 20
            divs[0] = 2
            cnt = 1
            x = (MOD - 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, (MOD - 1) // divs[i], MOD) == 1:
                        ok = False
                        break
                if ok:
                    return g
                g += 1
            
    
        g = primitive_root_constexpr()
        ig = pow(g, MOD - 2, MOD)
        W = [pow(g, (MOD - 1) >> i, MOD) for i in range(30)]
        iW = [pow(ig, (MOD - 1) >> i, MOD) for i in range(30)]
        def fft(k, f):
            for l in range(k, 0, -1):
                d = 1 << l - 1
                U = [1]
                for i in range(d):
                    U.append(U[-1] * W[l] % MOD)
                
                for i in range(1 << k - l):
                    for j in range(d):
                        s = i * 2 * d + j
                        f[s], f[s+d] = (f[s] + f[s+d]) % MOD, U[j] * (f[s] - f[s+d]) % MOD
        
        def ifft(k, f):
            for l in range(1, k + 1):
                d = 1 << l - 1
                for i in range(1 << k - l):
                    u = 1
                    for j in range(i * 2 * d, (i * 2 + 1) * d):
                        f[j+d] *= u
                        f[j], f[j+d] = (f[j] + f[j+d]) % MOD, (f[j] - f[j+d]) % MOD
                        u = u * iW[l] % MOD
     
        n0 = len(a) + len(b) - 1
        k = (n0).bit_length()
        n = 1 << k
        a = a + [0] * (n - len(a))
        b = b + [0] * (n - len(b))
        fft(k, a)
        fft(k, b)
        for i in range(n):
            a[i] = a[i] * b[i] % MOD
        ifft(k, a)
        invn = pow(n, MOD - 2, MOD)
        for i in range(n0):
            a[i] = a[i] * invn % MOD
        del a[n0:]
        return a
    
    def modinv(a, MOD):
        b = MOD
        u = 1
        v = 0
        while b:
            t = a // b
            a -= t * b
            u -= t * v
            a, b = b, a
            u, v = v, u
        u %= MOD
        if u < 0:
            u += m
        return u
    
    def Garner(M, R):
        m_prod = M[0]
        C = R[0]
        for m, r in zip(M[1:], R[1:]):
            t = (r - C) * modinv(m_prod, m) % m
            C += t * m_prod
            m_prod *= m
        return C
    
    
    MOD_ = [998244353, 167772161]
    n = len(A)
    lst = [[] for _ in range(2 * n - 1)]
    for mod in MOD_:
        C = convolve(A, B, mod)
        for i in range(2 * n - 1):
            lst[i].append(C[i])
    
    ans = [0] * (2 * n - 1)
    for i in range(2 * n - 1):
        ans[i] = Garner(MOD_, lst[i])
    return ans

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [i for i in range(1, n + 1)]
D = f(A, C)
E = f(B, C)
ans = [0] + [d + e for d, e in zip(D, E)]
print(*ans)
0