提供一个可以处理无理数的黑科技。
定义新的虚数单位 $i,i=\sqrt{5}.$
对于 $fib$ 数列的通项公式：
$$F_n = \dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]$$
将 $\sqrt{5}$ 视作虚数单位。原式可化为：
$$F_n = \dfrac{1}{i}\left[\left(\dfrac{1+i}{2}\right)^n-\left(\dfrac{1-i}{2}\right)^n\right]$$
需要注意： $i^2 = \sqrt{5}^2 = 5.$
$zz'=(a+bi)(c+di)=ac+(ad+bc)i+bdi^2=ac+5bd+(ad+bc)i$
答案是其实数部分。
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
ll p=1e9+7;
struct cplx{
ll a,b;
cplx(ll A=0,ll B=0): a(A), b(B) {}
cplx operator +(const cplx& tt)const{
ll u=a+tt.a,v=b+tt.b;
return cplx(u%p,v%p);
}
cplx operator -(const cplx& tt)const{
ll u=a-tt.a+p,v=b-tt.b+p;
return cplx(u%p,v%p);
}
cplx operator *(const cplx& tt)const{
ll u=a*tt.a+5*b*tt.b,v=a*tt.b+b*tt.a;
return cplx(u%p,v%p);
}
};
ll qpow(int a,int b){
ll base=a,res=1;
while(b){
if(b&1) res=res*base%p;
base=base*base%p, b>>=1;
}
return res;
}
cplx Qpow(cplx a,int b){
cplx base=a,res=cplx(1,0);
while(b){
if(b&1) res=res*base;
base=base*base, b>>=1;
}
return res;
}
signed main(){
ll n; cin>>n;
ll inv2=qpow(2,p-2);
cplx x=cplx(inv2,inv2);
cplx y=cplx(inv2,p-inv2);
cplx xx=Qpow(x,n),yy=Qpow(y,n);
cplx res=xx-yy;
ll ans=res.b;
printf("%lld\n",ans%p);
}
