結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2021-10-21 01:54:26 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 17,016 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 14,592 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-09-20 06:48:47 |
合計ジャッジ時間 | 2,817 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
import sysreadline=sys.stdin.readlineclass Polynomial:def __init__(self,polynomial,max_degree=-1,eps=0,mod=0):self.max_degree=max_degreeif self.max_degree!=-1 and len(polynomial)>self.max_degree+1:self.polynomial=polynomial[:self.max_degree+1]else:self.polynomial=polynomialself.mod=modself.eps=epsdef __eq__(self,other):if type(other)!=Polynomial:return Falseif len(self.polynomial)!=len(other.polynomial):return Falsefor i in range(len(self.polynomial)):if self.eps<abs(self.polynomial[i]-other.polynomial[i]):return Falsereturn Truedef __ne__(self,other):if type(other)!=Polynomial:return Trueif len(self.polynomial)!=len(other.polynomial):return Truefor i in range(len(self.polynomial)):if self.eps<abs(self.polynomial[i]-other.polynomial[i]):return Truereturn Falsedef __add__(self,other):if type(other)==Polynomial:summ=[0]*max(len(self.polynomial),len(other.polynomial))for i in range(len(self.polynomial)):summ[i]+=self.polynomial[i]for i in range(len(other.polynomial)):summ[i]+=other.polynomial[i]if self.mod:for i in range(len(summ)):summ[i]%=self.modelse:summ=[x for x in self.polynomial] if self.polynomial else [0]summ[0]+=otherif self.mod:summ[0]%=self.modwhile summ and abs(summ[-1])<=self.eps:summ.pop()summ=Polynomial(summ,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return summdef __sub__(self,other):if type(other)==Polynomial:diff=[0]*max(len(self.polynomial),len(other.polynomial))for i in range(len(self.polynomial)):diff[i]+=self.polynomial[i]for i in range(len(other.polynomial)):diff[i]-=other.polynomial[i]if self.mod:for i in range(len(diff)):diff[i]%=self.modelse:diff=[x for x in self.polynomial] if self.polynomial else [0]diff[0]-=otherif self.mod:diff[0]%=self.modwhile diff and abs(diff[-1])<=self.eps:diff.pop()diff=Polynomial(diff,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return diffdef __mul__(self,other):if type(other)==Polynomial:if self.max_degree==-1:prod=[0]*(len(self.polynomial)+len(other.polynomial)-1)for i in range(len(self.polynomial)):for j in range(len(other.polynomial)):prod[i+j]+=self.polynomial[i]*other.polynomial[j]else:prod=[0]*min(len(self.polynomial)+len(other.polynomial)-1,self.max_degree+1)for i in range(len(self.polynomial)):for j in range(min(len(other.polynomial),self.max_degree+1-i)):prod[i+j]+=self.polynomial[i]*other.polynomial[j]if self.mod:for i in range(len(prod)):prod[i]%=self.modelse:if self.mod:prod=[x*other%self.mod for x in self.polynomial]else:prod=[x*other for x in self.polynomial]while prod and abs(prod[-1])<=self.eps:prod.pop()prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return proddef __matmul__(self,other):assert type(other)==Polynomialif self.mod:prod=NTT(self.polynomial,other.polynomial)else:prod=FFT(self.polynomial,other.polynomial)if self.max_degree!=-1 and len(prod)>self.max_degree+1:prod=prod[:self.max_degree+1]while prod and abs(prod[-1])<=self.eps:prod.pop()prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return proddef __truediv__(self,other):if type(other)==Polynomial:assert other.polynomialfor n in range(len(other.polynomial)):if self.eps<abs(other.polynomial[n]):breakassert len(self.polynomial)>nfor i in range(n):assert abs(self.polynomial[i])<=self.epsself_polynomial=self.polynomial[n:]other_polynomial=other.polynomial[n:]if self.mod:inve=MOD(self.mod).Pow(other_polynomial[0],-1)else:inve=1/other_polynomial[0]quot=[]for i in range(len(self_polynomial)-len(other_polynomial)+1):if self.mod:quot.append(self_polynomial[i]*inve%self.mod)else:quot.append(self_polynomial[i]*inve)for j in range(len(other_polynomial)):self_polynomial[i+j]-=other_polynomial[j]*quot[-1]if self.mod:self_polynomial[i+j]%=self.modfor i in range(max(0,len(self_polynomial)-len(other_polynomial)+1),len(self_polynomial)):if self.eps<abs(self_polynomial[i]):assert self.max_degree!=-1self_polynomial=self_polynomial[-len(other_polynomial)+1:]+[0]*(len(other_polynomial)-1-len(self_polynomial))while len(quot)<=self.max_degree:self_polynomial.append(0)if self.mod:quot.append(self_polynomial[0]*inve%self.mod)self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1])%self.mod for i in range(1,len(self_polynomial))]else:quot.append(self_polynomial[0]*inve)self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1]) for i in range(1,len(self_polynomial))]breakquot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:assert self.eps<abs(other)if self.mod:inve=MOD(self.mod).Pow(other,-1)quot=Polynomial([x*inve%self.mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:quot=Polynomial([x/other for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quotdef __rtruediv__(self,other):assert self.polynomial and self.eps<self.polynomial[0]assert self.max_degree!=-1if self.mod:quot=[MOD(self.mod).Pow(self.polynomial[0],-1)]if self.mod==998244353:prim_root=3prim_root_inve=332748118else:prim_root=Primitive_Root(self.mod)prim_root_inve=MOD(self.mod).Pow(prim_root,-1)def DFT(polynomial,n,inverse=False):polynomial=polynomial+[0]*((1<<n)-len(polynomial))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])%modreturn polynomialelse:quot=[1/self.polynomial[0]]def DFT(polynomial,n,inverse=False):N=len(polynomial)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)]polynomial=polynomial+[0]*((1<<n)-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]for i in range(1<<n):polynomial[i]=round((polynomial[i]/(1<<n)).real)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])return polynomialfor n in range(self.max_degree.bit_length()):prev=quotif self.mod:polynomial=[x*y*y%self.mod for x,y in zip(DFT(self.polynomial[:1<<n+1],n+2),DFT(prev,n+2))]quot=DFT(polynomial,n+2,inverse=True)[:1<<n+1]else:polynomial=[x*y*y for x,y in zip(DFT(self.polynomial[:1<<n+1],n+2),DFT(prev,n+2))]quot=DFT(polynomial,n+2,inverse=True)[:1<<n+1]for i in range(1<<n):quot[i]=2*prev[i]-quot[i]if self.mod:quot[i]%=self.modfor i in range(1<<n,1<<n+1):quot[i]=-quot[i]if self.mod:quot[i]%=self.modquot=quot[:self.max_degree+1]for i in range(len(quot)):quot[i]*=otherif self.mod:quot[i]%=self.modreturn quotdef __floordiv__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quotdef __mod__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]while rema and abs(rema[-1])<=self.eps:rema.pop()rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return remadef __divmod__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]while rema and abs(rema[-1])<=self.eps:rema.pop()quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quot,remadef __neg__(self):if self.mod:nega=Polynomial([(-x)%self.mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:nega=Polynomial([-x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return negadef __pos__(self):posi=Polynomial([x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return posidef __bool__(self):return self.polynomialdef __getitem__(self,n):if n<=len(self.polynomial)-1:return self.polynomial[n]else:return 0def __setitem__(self,n,x):if self.mod:x%=self.modif self.max_degree==-1 or n<=self.max_degree:if n<=len(self.polynomial)-1:self.polynomial[n]=xelif self.eps<abs(x):self.polynomial+=[0]*(n-len(self.polynomial))+[x]def __call__(self,x):retu=0pow_x=1for i in range(len(self.polynomial)):retu+=pow_x*self.polynomial[i]pow_x*=xif self.mod:retu%=self.modpow_x%=self.modreturn retudef __str__(self):return "["+", ".join(map(str,self.polynomial))+"]"def degree(self):return len(self.polynomial)-1def Bostan_Mori(poly_nume,poly_deno,N,mod=0,fft=False,ntt=False):if type(poly_nume)==Polynomial:poly_nume=poly_nume.polynomialif type(poly_deno)==Polynomial:poly_deno=poly_deno.polynomialif ntt:convolve=NTTelif fft:convolve=FFTelse:def convolve(poly_nume,poly_deno):conv=[0]*(len(poly_nume)+len(poly_deno)-1)for i in range(len(poly_nume)):for j in range(len(poly_deno)):conv[i+j]+=poly_nume[i]*poly_deno[j]if mod:for i in range(len(conv)):conv[i]%=modreturn convwhile N:poly_deno_=[-x if i%2 else x for i,x in enumerate(poly_deno)]if N%2:poly_nume=convolve(poly_nume,poly_deno_)[1::2]else:poly_nume=convolve(poly_nume,poly_deno_)[::2]poly_deno=convolve(poly_deno,poly_deno_)[::2]if fft and mod:for i in range(len(poly_nume)):poly_nume[i]%=modfor i in range(len(poly_deno)):poly_deno[i]%=modN//=2return poly_nume[0]N=int(readline())mod=10**9+7fib_N=Bostan_Mori([0,1],[1,-1,-1],N,2*mod+2)ans=Bostan_Mori([0,1],[1,-1,-1],fib_N,mod=mod)print(ans)