結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2023-12-16 05:36:32 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,714 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 14,016 KB |
最終ジャッジ日時 | 2024-09-27 07:24:55 |
合計ジャッジ時間 | 8,575 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 TLE * 1 -- * 13 |
ソースコード
import sysreadline=sys.stdin.readlineimport mathdef FFT(polynomial0,polynomial1,digit=10**5):def DFT(polynomial,n,inverse=False):if inverse:primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)]else:primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)]if inverse:for bit in range(1,n+1):a=1<<bit-1for 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]*primitive_root[j<<n-bit],polynomial[s]-polynomial[t]*primitive_root[j<<n-bit]else:for bit in range(n,0,-1):a=1<<bit-1for 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],primitive_root[j<<n-bit]*(polynomial[s]-polynomial[t])def FFT_(polynomial0,polynomial1):N0=len(polynomial0)N1=len(polynomial1)N=N0+N1-1n=(N-1).bit_length()polynomial0=polynomial0+[0]*((1<<n)-N0)polynomial1=polynomial1+[0]*((1<<n)-N1)DFT(polynomial0,n)DFT(polynomial1,n)fft=[x*y for x,y in zip(polynomial0,polynomial1)]DFT(fft,n,inverse=True)fft=[round((fft[i]/(1<<n)).real) for i in range(N)]return fftif digit:N0=len(polynomial0)N1=len(polynomial1)N=N0+N1-1polynomial00,polynomial01=[None]*N0,[None]*N0polynomial10,polynomial11=[None]*N1,[None]*N1for i in range(N0):polynomial00[i],polynomial01[i]=divmod(polynomial0[i],digit)for i in range(N1):polynomial10[i],polynomial11[i]=divmod(polynomial1[i],digit)polynomial=[0]*Nfor i,x in enumerate(FFT_(polynomial00,polynomial10)):polynomial[i]+=x*(digit**2-digit)for i,x in enumerate(FFT_(polynomial01,polynomial11)):polynomial[i]-=x*(digit-1)for i,x in enumerate(FFT_([x1+x2 for x1,x2 in zip(polynomial00,polynomial01)],[x1+x2 for x1,x2 in zip(polynomial10,polynomial11)])):polynomial[i]+=x*digitelse:polynomial=FFT_(polynomial0,polynomial1)return polynomialN,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(FFT(A,R)):ans_lst[i%N]+=ansprint(*ans_lst)