結果

問題 No.1618 Convolution?
コンテスト
ユーザー ayaoni
提出日時 2021-07-22 23:53:00
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 1,799 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 165 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 355,236 KB
最終ジャッジ日時 2024-07-17 21:14:19
合計ジャッジ時間 18,028 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from cmath import pi,exp
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def LS2(): return list(sys.stdin.readline().rstrip())


def fft(A,n):
    roots = [exp(2j*pi/(2**i)) for i in range(n+1)]
    for i in range(n):
        m = 1 << (n-i-1)
        for start in range(1 << i):
            w = 1
            start *= m*2
            for j in range(m):
                A[start+j],A[start+j+m] = A[start+j]+A[start+j+m],(A[start+j]-A[start+j+m])*w
                w *= roots[n-i]
    return A


def inv_fft(A,n):
    inv_roots = [exp(-2j*pi/(2**i)) for i in range(n+1)]
    for i in range(n):
        m = 1 << i
        for start in range(1 << (n-i-1)):
            w = 1
            start *= m*2
            for j in range(m):
                A[start+j],A[start+j+m] = A[start+j]+A[start+j+m]*w,A[start+j]-A[start+j+m]*w
                w *= inv_roots[i+1]
    a = 1 << n
    for i in range(1 << n):
        A[i] /= a
    return A


def convolution(A,B):
    a,b = len(A),len(B)
    deg = a+b-2
    n = deg.bit_length()
    N = 1 << n
    A += [0]*(N-a)  # A の次数を 2冪-1 にする
    B += [0]*(N-b)  # B の次数を 2冪-1 にする
    A = fft(A,n)
    B = fft(B,n)
    C = [A[i]*B[i] for i in range(N)]
    C = inv_fft(C,n)
    for i in range(deg+1):
        C[i] = int(C[i].real+.5)
    return C[:deg+1]


N = I()
A = [0]+LI()
B = [0]+LI()
AB = [a+b for a,b in zip(A,B)]
X = [i for i in range(N+1)]
ANS = convolution(AB,X)
print(*ANS[1:])
0