結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2023-12-16 05:37:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 262 ms / 5,000 ms |
コード長 | 2,345 bytes |
コンパイル時間 | 376 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 115,216 KB |
最終ジャッジ日時 | 2024-09-27 07:25:19 |
合計ジャッジ時間 | 5,010 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
import sysreadline=sys.stdin.readlinemod=998244353def NTT(polynomial0,polynomial1):if len(polynomial0)*len(polynomial1)<=50:poly=[0]*(len(polynomial0)+len(polynomial1)-1)for i in range(len(polynomial0)):for j in range(len(polynomial1)):poly[i+j]+=polynomial0[i]*polynomial1[j]%modpoly[i+j]%=modreturn polyif mod==998244353:prim_root=3prim_root_inve=332748118else:prim_root=Primitive_Root(mod)prim_root_inve=MOD(mod).Pow(prim_root,-1)def DFT(polynomial,n,inverse=False):if inverse:for bit in range(1,n+1):a=1<<bit-1x=pow(prim_root,mod-1>>bit,mod)U=[1]for _ in range(a):U.append(U[-1]*x%mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t]*U[j])%mod,(polynomial[s]-polynomial[t]*U[j])%modx=pow((mod+1)//2,n,mod)for i in range(1<<n):polynomial[i]*=xpolynomial[i]%=modelse:for bit in range(n,0,-1):a=1<<bit-1x=pow(prim_root_inve,mod-1>>bit,mod)U=[1]for _ in range(a):U.append(U[-1]*x%mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t])%mod,U[j]*(polynomial[s]-polynomial[t])%modl=len(polynomial0)+len(polynomial1)-1n=(len(polynomial0)+len(polynomial1)-2).bit_length()polynomial0=polynomial0+[0]*((1<<n)-len(polynomial0))polynomial1=polynomial1+[0]*((1<<n)-len(polynomial1))DFT(polynomial0,n)DFT(polynomial1,n)ntt=[x*y%mod for x,y in zip(polynomial0,polynomial1)]DFT(ntt,n,inverse=True)ntt=ntt[:l]return nttN,Q=map(int,readline().split())A=list(map(int,readline().split()))R=[0]*Nfor r in map(int,readline().split()):R[(-r)%N]+=1ans_lst=[0]*Nfor i,ans in enumerate(NTT(A,R)):ans_lst[i%N]+=ansprint(*ans_lst)