結果

問題 No.1307 Rotate and Accumulate
ユーザー Wizist
提出日時 2020-12-05 05:05:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,584 ms / 5,000 ms
コード長 1,150 bytes
コンパイル時間 529 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 305,940 KB
最終ジャッジ日時 2024-09-15 10:25:51
合計ジャッジ時間 16,058 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#!/usr/bin/env python3
#
# No.1307 Rotate and Accumulate
#
import sys, os, math
def fft(a, inverse=False):
    n = 1
    while n < len(a): n <<= 1
    if len(a) < n: a += [0] * (n - len(a))
    j, k = 0, 1
    for i in range(1, n):
        bit = n >> 1
        while j & bit: j ^= bit; bit >>= 1
        j ^= bit
        if i < j: a[i], a[j] = a[j], a[i]
    while k < n:
        wk = math.cos(math.pi / k) + math.sin(-math.pi / k if inverse else math.pi / k) * 1j
        for i in range(0, n, 2 * k):
            w = 1 + 0j
            for j in range(k):
                u, v = a[i + j], a[i + j + k] * w
                a[i + j] = u + v
                a[i + j + k] = u - v
                w *= wk
        k *= 2
    if inverse:
        for i in range(n): a[i] /= n
def multiply(a, b):
    n = 1
    while n < len(a) + len(b): n <<= 1
    f, g, r = [0] * n, [0] * n, [0] * n
    for i, v in enumerate(a): f[i] = v
    for i, v in enumerate(b): g[i] = v
    fft(f); fft(g)
    for i in range(n): f[i] *= g[i]
    fft(f, True)
    for i, v in enumerate(f): r[i] = round(v.real)
    return r
def read_ints(): return list(map(int, input().split()))
n, q = read_ints()
a, r = read_ints(), read_ints()
f = a + a
g = [0] * (n + 1)
for x in r: g[n - x] += 1
c = multiply(f, g)
print(" ".join(map(str, c[n:n + n])))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0