結果

問題 No.754 畳み込みの和
ユーザー ygd.ygd.
提出日時 2022-03-05 16:46:48
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,627 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 10,788 KB
実行使用メモリ 55,928 KB
最終ジャッジ日時 2023-09-27 04:19:54
合計ジャッジ時間 4,301 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
#input = sys.stdin.readline
input = sys.stdin.buffer.readline #文字列はダメ
#sys.setrecursionlimit(1000000)
#import bisect
#import itertools
#import random
#from heapq import heapify, heappop, heappush
#from collections import defaultdict 
#from collections import deque
#import copy
#import math
#from functools import lru_cache
#@lru_cache(maxsize=None)
MOD = pow(10,9) + 7
#MOD = 998244353
#dx = [1,0,-1,0]
#dy = [0,1,0,-1]

import numpy as np

#int64を超えるので大きいと答えがずれる？

def convolve(f, g):
    """多項式 f, g の積を計算する。
 
    Parameters
    ----------
    f : np.ndarray (int64)
        f[i] に、x^i の係数が入っている
 
    g : np.ndarray (int64)
        g[i] に、x^i の係数が入っている
 
 
    Returns
    -------
    h : np.ndarray
        f,g の積
    """
    # h の長さ以上の n=2^k を計算
    fft_len = 1
    while 2 * fft_len < len(f) + len(g) - 1:
        fft_len *= 2
    fft_len *= 2
 
    # フーリエ変換
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
 
    # 各点積
    Fh = Ff * Fg
 
    # フーリエ逆変換
    h = np.fft.irfft(Fh, fft_len)
 
    # 小数になっているので、整数にまるめる
    h = np.rint(h).astype(np.int64)
 
    return h[:len(f) + len(g) - 1]

def main():
    n = int(input())
    A = [int(input()) for _ in range(n+1)]
    B = [int(input()) for _ in range(n+1)]
    print(A)
    print(B)
    C = convolve(A,B)
    ans = 0
    for i in range(n+1):
        ans += C[i]
        ans %= MOD
    print(ans)

    
if __name__ == '__main__':
    main()
0