結果
問題 | No.754 畳み込みの和 |
ユーザー | vwxyz |
提出日時 | 2021-10-08 01:41:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,815 ms / 5,000 ms |
コード長 | 2,523 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 310,040 KB |
最終ジャッジ日時 | 2024-07-23 03:15:13 |
合計ジャッジ時間 | 8,049 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,799 ms
310,036 KB |
testcase_01 | AC | 1,815 ms
310,040 KB |
testcase_02 | AC | 1,812 ms
310,040 KB |
ソースコード
import sys readline=sys.stdin.readline import math def FFT(polynomial0,polynomial1,digit=10**5): def DFT(polynomial,n,inverse=False): if inverse: primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)] else: primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)] if inverse: for bit in range(1,n+1): a=1<<bit-1 for i in range(1<<n-bit): for j in range(a): s=i*2*a+j t=s+a polynomial[s],polynomial[t]=polynomial[s]+polynomial[t]*primitive_root[j<<n-bit],polynomial[s]-polynomial[t]*primitive_root[j<<n-bit] else: for bit in range(n,0,-1): a=1<<bit-1 for i in range(1<<n-bit): for j in range(a): s=i*2*a+j t=s+a polynomial[s],polynomial[t]=polynomial[s]+polynomial[t],primitive_root[j<<n-bit]*(polynomial[s]-polynomial[t]) def FFT_(polynomial0,polynomial1): N0=len(polynomial0) N1=len(polynomial1) N=N0+N1-1 n=(N-1).bit_length() polynomial0=polynomial0+[0]*((1<<n)-N0) polynomial1=polynomial1+[0]*((1<<n)-N1) DFT(polynomial0,n) DFT(polynomial1,n) fft=[x*y for x,y in zip(polynomial0,polynomial1)] DFT(fft,n,inverse=True) fft=[round((fft[i]/(1<<n)).real) for i in range(N)] return fft N0=len(polynomial0) N1=len(polynomial1) N=N0+N1-1 polynomial00,polynomial01=[None]*N0,[None]*N0 polynomial10,polynomial11=[None]*N1,[None]*N1 for i in range(N0): polynomial00[i],polynomial01[i]=divmod(polynomial0[i],digit) for i in range(N1): polynomial10[i],polynomial11[i]=divmod(polynomial1[i],digit) polynomial=[0]*(N) a=digit**2-digit for i,x in enumerate(FFT_(polynomial00,polynomial10)): polynomial[i]+=x*a a=digit-1 for i,x in enumerate(FFT_(polynomial01,polynomial11)): polynomial[i]-=x*a for i,x in enumerate(FFT_([x1+x2 for x1,x2 in zip(polynomial00,polynomial01)],[x1+x2 for x1,x2 in zip(polynomial10,polynomial11)])): polynomial[i]+=x*digit return polynomial N=int(readline()) A=[int(readline()) for i in range(N+1)] B=[int(readline()) for i in range(N+1)] mod=10**9+7 ans=sum(FFT(A,B)[:N+1])%mod print(ans)