結果

問題 No.1618 Convolution?
コンテスト
ユーザー ayaoni
提出日時 2021-07-22 21:32:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,002 bytes
コンパイル時間 254 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 480,460 KB
最終ジャッジ日時 2024-07-17 16:39:12
合計ジャッジ時間 5,214 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

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())


N = I()
A = LI()
B = LI()


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]


X0 = [0]+[A[i-1]+i for i in range(1,N+1)]
Y0 = [0]+[B[i-1]+i for i in range(1,N+1)]
X1 = [0]+A
Y1 = [0]+B
X2 = [i for i in range(N+1)]
Y2 = [i for i in range(N+1)]

Z0 = convolution(X0,Y0)
Z1 = convolution(X1,Y1)
Z2 = convolution(X2,Y2)
ANS = [z0-z1-z2 for z0,z1,z2 in zip(Z0[1:],Z1[1:],Z2[1:])]
print(*ANS)
0