【洛谷P5303】【GXOI/GZOI2019】—逼死强迫症（斐波那契数列）

手玩一下可以显然的发现

$ans=2sum_{i=0}^{n-3}sum_{j=0}^{n-3-i}f[i+1]f[j+1]$

利用 $f[i]=frac{(frac{1+sqrt 5}{2})^i-(frac{1-sqrt 5}{2})^i}{sqrt 5}$

暴力拆开化简就是几个等比数列求和

然后用大力乱推一波就完了

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>  
cs int mod=1e9+7;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline void Add(int &a,int b){(a+=b)>=mod?a-=mod:0;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline void Dec(int &a,int b){(a-=b)<0?a+=mod:0;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline void Mul(int &a,int b){a=1ll*a*b%mod;}
inline int ksm(int a,int b,int res=1){if(b<0)return 0;for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline int Inv(int x){return ksm(x,mod-2);}
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
cs int inv2=Inv(2),inv5=Inv(5);
struct plx{
	int x,y;
	plx(int _x=0,int _y=0):x(_x),y(_y){}
	friend inline plx operator +(cs plx &a,cs plx &b){
		return plx(add(a.x,b.x),add(a.y,b.y));
	}
	friend inline plx operator -(cs plx &a,cs plx &b){
		return plx(dec(a.x,b.x),dec(a.y,b.y));
	}
	friend inline plx operator *(cs plx &a,cs plx &b){
		return plx((1ll*a.x*b.x+5ll*a.y*b.y)%mod,(1ll*a.x*b.y+1ll*a.y*b.x)%mod);
	}
	friend inline plx operator -(cs plx &a,cs int &b){
		return plx(dec(a.x,b),a.y);
	}
	friend inline plx operator +(cs plx &a,cs int &b){
		return plx(add(a.x,b),a.y);
	}
	friend inline plx operator *(cs plx &a,cs int &b){
		return plx(mul(a.x,b),mul(a.y,b));
	}
};
inline plx pksm(plx a,int b){
	if(b<0)return plx(0,0);
	plx res(1,0);
	for(;b;b>>=1,a=a*a)if(b&1)res=res*a;
	return res;
}
inline plx pInv(plx x){
	return plx(x.x,dec(0,x.y))*Inv(((1ll*x.x*x.x-5ll*x.y*x.y)%mod+mod)%mod);
}
inline plx calc(plx x,plx y,int n){
	if(n<=2)return plx(0,0);
	plx dx=pInv(x-1),dy=pInv(y-1),p=y*pInv(x);
	plx res=(pksm(y,n-1)-y)*dy*x-(pksm(x,n)-x*x)*dx;
	res=res-(pksm(p,n-2)-1)*(pInv(p-1))*(pksm(x,n-1)*y);
	res=res+(n-2)*pksm(x,n);
	return res*dx;
}
plx X=plx(inv2,inv2),Y=plx(inv2,dec(0,inv2));
int main(){
	int T=read();
	while(T--){
		int n=read();
		plx ans=calc(X,Y,n)+calc(Y,X,n);
		cout<<mul(mul((ans.x),inv5),2)<<'
';
	}
}

【洛谷P5303】【GXOI/GZOI2019】—逼死强迫症（斐波那契数列）

相关推荐