結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlines# 原子根のべき乗で書いて、多項式に帰着import numpy as npp = int(readline())A = np.array([0] + readline().split(), np.int64)B = np.array([0] + readline().split(), np.int64)MOD = 998244353def make_prime(U):is_prime = np.zeros(U,np.bool)is_prime[2] = 1is_prime[3::2] = 1M = int(U**.5)+1for p in range(3,M,2):if is_prime[p]:is_prime[p*p::p+p] = 0return is_prime, is_prime.nonzero()[0]def find_primitive_root(p):import randomif p == 2:return 1_, primes = make_prime(p)e = p - 1div = [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):continuereturn rdef make_power(a, L, MOD=MOD):B = L.bit_length()x = np.empty((1<<B), np.int64)x[0] = 1for n in range(B):x[1<<n:1<<(n+1)] = x[:1<<n] * a % MODa *= a; a %= MODreturn 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.irfftLf = len(f); Lg = len(g); L = Lf + Lg - 1fft_len = 1 << L.bit_length()fl = f & (1 << 15) - 1; fh = f >> 15gl = g & (1 << 15) - 1; gh = g >> 15conv = lambda f,g: ifft(fft(f,fft_len) * fft(g,fft_len))[:L]x = conv(fl, gl) % MODy = conv(fl+fh, gl+gh) % MODz = conv(fh, gh) % MODa, b, c = map(lambda x: (x + .5).astype(np.int64), [x,y,z])return (a + ((b - a - c) << 15) + (c << 30)) % MODfg = fft_convolve(f,g)L = len(fg); fg[0:L-(p-1)] += fg[p-1:L]; fg = fg[:p-1]; fg %= MODanswer = fg[log[1:]]print(' '.join(answer.astype(str)))