結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
|
提出日時 | 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 |
ソースコード
import sysinput = 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 = nM = int(-(-n**0.5//1))+1if m is not None:M = min(m+1, M)for i in range(2, M+1):if tmp<i:breakif tmp%i==0:cnt=0while tmp%i==0:cnt+=1tmp //= if[i] = cntif tmp!=1:f[tmp] = 1if not f:f[n] = 1return fdef primitive_root(m):if m == 2:return 1if m == 167772161:return 3if m == 469762049:return 3if m == 754974721:return 11if m == 998244353:return 3g = 2f = factor(m-1)while True:if all(pow(g,(p-1)//k,p)!=1 for k in f.keys()):breakg += 1return g# FFTimport numpy as npM = 998244353def fft(a,b):l = 1while 2 * l < len(a) + len(b) - 1:l *= 2l *= 2c = 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 hdef fft_large(a,b):"""精度が足りないときはこちら"""d = 1<<10a1, 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) % Mbb = fft(a2,b2) % Mcc = fft(a3,b3) % Mdd = (fft(a1+a2, b1+b2) - (aa+bb)) % Mee = (fft(a2+a3, b2+b3) - (bb+cc)) % Mff = (fft(a1+a3, b1+b3) - (aa+cc)) % Mh = (((aa*d*d)%M)*d*d + ((dd*d*d)%M)*d + (bb+ff)*d*d + ee*d + cc) % Mreturn hp = 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-2b = [None]*(p-1)g = primitive_root(p)v = 1for i in range(p-1):a[i] = aa[v-1]b[i] = bb[v-1]v *= gv %= pa = np.array(a, dtype=np.int64)b = np.array(b, dtype=np.int64)c = fft_large(a,b)ans = [0]*(p-1)v = 1for i in range(2*p-3):ans[v-1] += c[i]ans[v-1] %= Mv *= gv %= pwrite(" ".join(map(str, ans)))