結果

問題 No.931 Multiplicative Convolution
ユーザー maspy
提出日時 2020-01-02 13:38:13
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,142 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 47,600 KB
最終ジャッジ日時 2024-11-22 18:00:27
合計ジャッジ時間 11,189 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1 RE * 2
other RE * 14
権限があれば一括ダウンロードができます

ソースコード

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
#
import numpy as np
p = int(readline())
A = np.array([0] + readline().split(), np.int64)
B = np.array([0] + readline().split(), np.int64)
MOD = 998244353
def make_prime(U):
is_prime = np.zeros(U,np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
M = int(U**.5)+1
for p in range(3,M,2):
if is_prime[p]:
is_prime[p*p::p+p] = 0
return is_prime, is_prime.nonzero()[0]
def find_primitive_root(p):
import random
if p == 2:
return 1
_, primes = make_prime(p)
e = p - 1
div = [q for q in primes if not e % q]
test_n = [e // q for q in div]
while True:
r = random.randint(1,p)
if any(pow(r,int(n),p) == 1 for n in test_n):
continue
return r
def make_power(a, L, MOD=MOD):
B = L.bit_length()
x = np.empty((1<<B), np.int64)
x[0] = 1
for n in range(B):
x[1<<n:1<<(n+1)] = x[:1<<n] * a % MOD
a *= a; a %= MOD
return x[:L]
r = find_primitive_root(p)
exp = make_power(r,p-1,p)
log = np.zeros(p,np.int32)
log[exp] = np.arange(p-1)
f = A[exp]; g = B[exp]
def fft_convolve(f, g, MOD = MOD):
"""
() f, g 15 bit
30 bit 250000
"""
fft = np.fft.rfft; ifft = np.fft.irfft
Lf = len(f); Lg = len(g); L = Lf + Lg - 1
fft_len = 1 << L.bit_length()
fl = f & (1 << 15) - 1; fh = f >> 15
gl = g & (1 << 15) - 1; gh = g >> 15
conv = lambda f,g: ifft(fft(f,fft_len) * fft(g,fft_len))[:L]
x = conv(fl, gl) % MOD
y = conv(fl+fh, gl+gh) % MOD
z = conv(fh, gh) % MOD
a, b, c = map(lambda x: (x + .5).astype(np.int64), [x,y,z])
return (a + ((b - a - c) << 15) + (c << 30)) % MOD
fg = fft_convolve(f,g)
L = len(fg); fg[0:L-(p-1)] += fg[p-1:L]; fg = fg[:p-1]; fg %= MOD
answer = fg[log[1:]]
print(' '.join(answer.astype(str)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0