結果

問題 No.1307 Rotate and Accumulate
ユーザー WizistWizist
提出日時 2020-12-05 22:30:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 921 ms / 5,000 ms
コード長 1,732 bytes
コンパイル時間 726 ms
コンパイル使用メモリ 87,236 KB
実行使用メモリ 120,900 KB
最終ジャッジ日時 2023-10-14 09:53:59
合計ジャッジ時間 11,314 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
71,616 KB
testcase_01 AC 59 ms
71,284 KB
testcase_02 AC 58 ms
71,308 KB
testcase_03 AC 70 ms
76,292 KB
testcase_04 AC 72 ms
76,528 KB
testcase_05 AC 64 ms
76,180 KB
testcase_06 AC 68 ms
76,400 KB
testcase_07 AC 59 ms
71,608 KB
testcase_08 AC 483 ms
97,976 KB
testcase_09 AC 477 ms
100,592 KB
testcase_10 AC 486 ms
100,556 KB
testcase_11 AC 470 ms
92,548 KB
testcase_12 AC 490 ms
100,192 KB
testcase_13 AC 151 ms
89,020 KB
testcase_14 AC 281 ms
91,148 KB
testcase_15 AC 911 ms
120,260 KB
testcase_16 AC 921 ms
120,224 KB
testcase_17 AC 907 ms
120,212 KB
testcase_18 AC 914 ms
117,008 KB
testcase_19 AC 897 ms
120,680 KB
testcase_20 AC 899 ms
120,900 KB
testcase_21 AC 61 ms
71,176 KB
権限があれば一括ダウンロードができます

ソースコード

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
	root_1 = pow(root, mod - 2, mod)
	r = [0] * 30; ir = [0] * 30
	for i in range(len(r)):
		r[i] = mod - pow(root, (mod - 1) >> (i + 2), mod)
		ir[i] = pow(r[i], mod - 2, mod)
	n = 1
	while n < len(a): n <<= 1
	if len(a) < n: a += [0] * (n - len(a))
	if not inverse:
		k = n >> 1
		while k != 0:
			w = 1
			wk = root; i = k
			while i < root_pw: wk = wk * wk % mod; i <<= 1
			t = 0
			for s in range(0, n, 2 * k):
				for i in range(s, s + k):
					u = a[i]; v = a[i + k] * w % mod
					a[i] = (u + v) % mod
					a[i + k] = (u - v + mod) % mod
				t += 1
				z = 0; x = t
				while x and x % 2 == 0: z += 1; x >>= 1
				w = w * r[z] % mod
			k >>= 1
	else:
		k = 1
		while k < n:
			w = 1
			wk = root_1; i = k
			while i < root_pw: wk = wk * wk % mod; i <<= 1
			t = 0
			for s in range(0, n, 2 * k):
				for i in range(s, s + k):
					u = a[i]; v = a[i + k]
					a[i] = (u + v) % mod
					a[i + k] = (u - v + mod) % mod * w % mod
				t += 1
				z = 0; x = t
				while x and x % 2 == 0: z += 1; x >>= 1
				w = w * ir[z] % mod
			k <<= 1
		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