結果

問題 No.1307 Rotate and Accumulate
ユーザー WizistWizist
提出日時 2020-12-05 05:05:28
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 1,342 ms / 5,000 ms
コード長 1,150 bytes
コンパイル時間 464 ms
コンパイル使用メモリ 87,236 KB
実行使用メモリ 308,308 KB
最終ジャッジ日時 2023-10-13 13:37:03
合計ジャッジ時間 13,276 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 61 ms
71,896 KB
testcase_01 AC 64 ms
71,996 KB
testcase_02 AC 61 ms
71,540 KB
testcase_03 AC 68 ms
76,672 KB
testcase_04 AC 71 ms
76,712 KB
testcase_05 AC 67 ms
76,848 KB
testcase_06 AC 67 ms
76,796 KB
testcase_07 AC 61 ms
71,736 KB
testcase_08 AC 596 ms
284,272 KB
testcase_09 AC 564 ms
284,832 KB
testcase_10 AC 576 ms
282,824 KB
testcase_11 AC 562 ms
283,256 KB
testcase_12 AC 569 ms
282,276 KB
testcase_13 AC 122 ms
90,424 KB
testcase_14 AC 257 ms
142,892 KB
testcase_15 AC 1,227 ms
301,964 KB
testcase_16 AC 1,288 ms
301,988 KB
testcase_17 AC 1,249 ms
301,916 KB
testcase_18 AC 1,250 ms
308,308 KB
testcase_19 AC 1,262 ms
301,952 KB
testcase_20 AC 1,342 ms
306,312 KB
testcase_21 AC 60 ms
71,584 KB
権限があれば一括ダウンロードができます

ソースコード

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])))
0