結果

問題 No.1307 Rotate and Accumulate
ユーザー vwxyz
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
readline=sys.stdin.readline
import math
def 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-1
for i in range(1<<n-bit):
for j in range(a):
s=i*2*a+j
t=s+a
polynomial[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-1
for i in range(1<<n-bit):
for j in range(a):
s=i*2*a+j
t=s+a
polynomial[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-1
n=(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 fft
if digit:
N0=len(polynomial0)
N1=len(polynomial1)
N=N0+N1-1
polynomial00,polynomial01=[None]*N0,[None]*N0
polynomial10,polynomial11=[None]*N1,[None]*N1
for 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]*N
for 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*digit
else:
polynomial=FFT_(polynomial0,polynomial1)
return polynomial
N,Q=map(int,readline().split())
A=list(map(int,readline().split()))
R=[0]*N
for r in map(int,readline().split()):
R[(-r)%N]+=1
ans_lst=[0]*N
for i,ans in enumerate(FFT(A,R)):
ans_lst[i%N]+=ans
print(*ans_lst)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0