結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
![]() |
提出日時 | 2024-11-14 03:23:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 262 ms / 2,000 ms |
コード長 | 2,918 bytes |
コンパイル時間 | 253 ms |
コンパイル使用メモリ | 82,264 KB |
実行使用メモリ | 117,612 KB |
最終ジャッジ日時 | 2024-11-14 03:23:44 |
合計ジャッジ時間 | 4,082 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
import sysinput = sys.stdin.readlinemod=998244353P=int(input())A=list(map(int,input().split()))B=list(map(int,input().split()))if P==2:print(A[0]*B[0]%mod)exit()# FFT# mod=998244353 における、NTTによる高速フーリエ変換、畳み込み# 他の提出を参考にしており、あまり理解できていません……Weight=[1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897,350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432, 0]Weight_inv=[1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727,358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224, 0]def fft(A,n,h,inverse=0):if inverse==0:for i in range(h):m=1<<(h-i-1)for j in range(1<<i):w=1ij=j*m*2wk=Weight[h-i]for k in range(m):A[ij+k],A[ij+k+m]=(A[ij+k]+A[ij+k+m])%mod,(A[ij+k]-A[ij+k+m])*w%modw=w*wk%modelse:for i in range(h):m=1<<ifor j in range(1<<(h-i-1)):w=1ij=j*m*2wk=Weight_inv[i+1]for k in range(m):A[ij+k],A[ij+k+m]=(A[ij+k]+A[ij+k+m]*w)%mod,(A[ij+k]-A[ij+k+m]*w)%modw=w*wk%modif inverse==1:INV_n=pow(n,mod-2,mod)for i in range(n):A[i]=A[i]*INV_n%modreturn Adef convolution(A,B):FFTLEN=len(A)+len(B)-1h=FFTLEN.bit_length()LEN=2**hA+=[0]*(LEN-len(A)) # A,Bのサイズを2ベキに揃えるB+=[0]*(LEN-len(B))A_FFT=fft(A,LEN,h)B_FFT=fft(B,LEN,h)for i in range(len(A)):A[i]=A[i]*B[i]%modA=fft(A,LEN,h,1)return A[:FFTLEN]# Pの原始根rootを求める。# P-1の約数を求める。x=(P-1)L=int((P-1)**(1/2))FACT=dict()for i in range(2,L+2):while x%i==0:FACT[i]=FACT.get(i,0)+1x=x//iif x!=1:FACT[x]=FACT.get(x,0)+1# 2から順にチェックfor i in range(2,P):for f in FACT:if pow(i,(P-1)//f,P)==1:breakelse:root=ibreakLIST=[1]for i in range(P):LIST.append(LIST[-1]*root%P)A2=[]B2=[]for i in range(P-1):A2.append(A[LIST[i]-1])B2.append(B[LIST[i]-1])#print(A)#print(A2)X=convolution(A2,B2)ANS=[0]*(P-1)for i in range(len(X)):k=i%(P-1)ANS[k]=(ANS[k]+X[i])%mod#print(*ANS)ANS2=[0]*(P-1)for i in range(P-1):ANS2[LIST[i]-1]=ANS[i]print(*ANS2)