結果

問題 No.931 Multiplicative Convolution
ユーザー shotoyooshotoyoo
提出日時 2020-09-23 23:35:50
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,122 ms / 2,000 ms
コード長 2,489 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 84,492 KB
最終ジャッジ日時 2024-06-28 04:41:18
合計ジャッジ時間 16,531 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")
def factor(n, m=None):
# m
f = {}
tmp = n
M = int(-(-n**0.5//1))+1
if m is not None:
M = min(m+1, M)
for i in range(2, M+1):
if tmp<i:
break
if tmp%i==0:
cnt=0
while tmp%i==0:
cnt+=1
tmp //= i
f[i] = cnt
if tmp!=1:
f[tmp] = 1
if not f:
f[n] = 1
return f
def primitive_root(m):
if m == 2:
return 1
if m == 167772161:
return 3
if m == 469762049:
return 3
if m == 754974721:
return 11
if m == 998244353:
return 3
g = 2
f = factor(m-1)
while True:
if all(pow(g,(p-1)//k,p)!=1 for k in f.keys()):
break
g += 1
return g
# FFT
import numpy as np
M = 998244353
def fft(a,b):
l = 1
while 2 * l < len(a) + len(b) - 1:
l *= 2
l *= 2
c = np.fft.irfft((np.fft.rfft(a,l))*(np.fft.rfft(b,l)),l)
c = np.rint(c).astype(np.int64)
return c
# def fft_large(a,b):
# d = 30000
# a1, a2 = np.divmod(a,d)
# b1, b2 = np.divmod(b,d)
# aa = fft(a1,b1) % M
# bb = fft(a2,b2) % M
# cc = (fft(a1+a2, b1+b2) - (aa+bb)) % M
# h = (((aa*d)%M)*d + cc*d + bb) % M
# return h
def fft_large(a,b):
"""
"""
d = 1<<10
a1, a2 = np.divmod(a,d*d)
a2, a3 = np.divmod(a2,d)
b1, b2 = np.divmod(b,d*d)
b2, b3 = np.divmod(b2,d)
aa = fft(a1,b1) % M
bb = fft(a2,b2) % M
cc = fft(a3,b3) % M
dd = (fft(a1+a2, b1+b2) - (aa+bb)) % M
ee = (fft(a2+a3, b2+b3) - (bb+cc)) % M
ff = (fft(a1+a3, b1+b3) - (aa+cc)) % M
h = (((aa*d*d)%M)*d*d + ((dd*d*d)%M)*d + (bb+ff)*d*d + ee*d + cc) % M
return h
p = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
a = [None]*(p-1) # a[i] = A[g^i] i=0,1,...,p-2
b = [None]*(p-1)
g = primitive_root(p)
v = 1
for i in range(p-1):
a[i] = aa[v-1]
b[i] = bb[v-1]
v *= g
v %= p
a = np.array(a, dtype=np.int64)
b = np.array(b, dtype=np.int64)
c = fft_large(a,b)
ans = [0]*(p-1)
v = 1
for i in range(2*p-3):
ans[v-1] += c[i]
ans[v-1] %= M
v *= g
v %= p
write(" ".join(map(str, ans)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0