結果
問題 | No.1521 Playing Musical Chairs Alone |
ユーザー |
![]() |
提出日時 | 2021-05-28 22:15:34 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 543 ms / 2,000 ms |
コード長 | 2,291 bytes |
コンパイル時間 | 252 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 44,696 KB |
最終ジャッジ日時 | 2024-11-07 09:43:21 |
合計ジャッジ時間 | 17,158 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import numpy as npimport sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesmod=10**9+7inv2=499122177def fft_len(N):fftlen=1beki=0while fftlen<N:fftlen*=2beki+=1return fftlen,bekidef FPStime(L,R):fftlen,beki=fft_len(len(L)+len(R))FS=np.fft.rfft(L, fftlen)FT=np.fft.rfft(R, fftlen)Fh=FS*FTh = np.fft.irfft(Fh, fftlen)h = np.rint(h).astype(np.int64)return h[:len(L) + len(R) - 1]def FPStime2(L,R,mod):f1,f2=np.divmod(L,1<<15)g1,g2=np.divmod(R,1<<15)a=FPStime(f1,g1)%modc=FPStime(f2,g2)%modb=(FPStime(f1+f2,g1+g2)-(a+c))%modh=(a<<30)+(b<<15)+creturn h%moddef FPSinv(f):"""1/f=gをreturn"""f=np.array(f, np.int64)this_len,this_roop=fft_len(len(f))c=pow(int(f[0]),-1,mod)g=np.array([c], np.int64)a=1for i in range(this_roop):a*=2S=FPStime2(g,f,mod)[:a]S*=-1S[0]+=2S=[i%mod for i in S]g=FPStime2(g,S,mod)g=g[:a]g=[i%mod for i in g]return g[:len(f)+1]def FPSsqrt(f):"""sqrt(f)=gをreturn"""f=np.array(f, np.float64)g=np.array([f[0]**0.5], np.float64)this_len,this_roop=fft_len(len(f))a=1for i in range(this_roop):a*=2g=FPSplus(FPStime(f,FPSinv(g)),g)g=g*inv2g=g[:a]g=[i%mod for i in g]return g[:len(f)]def keisu(P,Q,N):#P(x)/Q(x)のx^Nの係数Q2=list()for i in range(len(Q)):if N==0:return P[0]if i%2==0:Q2.append(Q[i])else:Q2.append(-Q[i])S=FPStime2(Q,Q2,mod)V=list()for i in range(0,len(S),2):V.append(S[i])Ue=list()Uo=list()P=FPStime2(P,Q2,mod)for i in range(len(P)):if i%2==0:Ue.append(P[i])else:Uo.append(P[i])if N%2==0:return keisu(Ue,V,N//2)else:return keisu(Uo,V,N//2)from functools import lru_cache@lru_cache(maxsize=1000000)def beki(a):if a==1:return fif a%2==0:L=FPStime2(beki(a//2),beki(a//2),mod)else:L=FPStime2(FPStime2(beki(a//2),beki(a//2),mod),f,mod)C=[0]*(N)for i in range(len(L)):C[i%(N)]+=L[i]C[i%N]%=modreturn CN,K,L=map(int,input().split())f=[0]+[1]*Lf=f+[0]*(N-len(f))if N==L:f=[1]*Nansl=beki(K)for i in ansl:print(i)