結果

問題 No.1307 Rotate and Accumulate
コンテスト
ユーザー Wizist
提出日時 2020-12-05 14:20:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,314 bytes
コンパイル時間 447 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 116,412 KB
最終ジャッジ日時 2024-09-15 17:12:14
合計ジャッジ時間 12,784 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
#
# No.1307 Rotate and Accumulate
#
import sys, os, math

def ntt(a, inverse=False):
	# mod, root, root_pw = (119 << 23) + 1, 3, 1 << 23
	mod, root, root_pw = 7340033, 5, 1 << 20
	root_1, n = pow(root, mod - 2, mod), 1
	while n < len(a): n <<= 1
	if len(a) < n: a += [0] * (n - len(a))
	j = 0
	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]
	k = 2
	while k <= n:
		wk, i = root_1 if inverse else root, k
		while i < root_pw: wk = wk * wk % mod; i <<= 1
		for i in range(0, n, k):
			w = 1
			for j in range(k // 2):
				u, v = a[i + j], a[i + j + k // 2] * w % mod
				a[i + j] = (u + v) % mod
				a[i + j + k // 2] = (u - v + mod) % mod
				w = w * wk % mod
		k <<= 1
	if inverse:
		n_1 = pow(n, mod - 2, mod)
		for i in range(len(a)): a[i] = a[i] * n_1 % mod

def multiply(a, b):
	n = 1
	while n < len(a) + len(b): n <<= 1
	f, g = [0] * n, [0] * n
	for i, v in enumerate(a): f[i] = v
	for i, v in enumerate(b): g[i] = v
	ntt(f); ntt(g)
	for i in range(n): f[i] *= g[i]
	ntt(f, True)
	return f

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