結果
問題 | 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 np import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines mod=10**9+7 inv2=499122177 def fft_len(N): fftlen=1 beki=0 while fftlen<N: fftlen*=2 beki+=1 return fftlen,beki def 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*FT h = 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)%mod c=FPStime(f2,g2)%mod b=(FPStime(f1+f2,g1+g2)-(a+c))%mod h=(a<<30)+(b<<15)+c return h%mod def 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=1 for i in range(this_roop): a*=2 S=FPStime2(g,f,mod)[:a] S*=-1 S[0]+=2 S=[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=1 for i in range(this_roop): a*=2 g=FPSplus(FPStime(f,FPSinv(g)),g) g=g*inv2 g=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 f if 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]%=mod return C N,K,L=map(int,input().split()) f=[0]+[1]*L f=f+[0]*(N-len(f)) if N==L: f=[1]*N ansl=beki(K) for i in ansl: print(i)