|
斐波那契數(shù)列是一個(gè)很神奇的東西，今天我們就來談一談它。 前言：本篇博客中會(huì)有大量的公式，每一個(gè)公式都會(huì)給出嚴(yán)謹(jǐn)?shù)淖C明（證明方法都是最嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)歸納法） 1.從特征方程說起前言：事實(shí)上，特征方程所求得的通項(xiàng)公式在實(shí)際應(yīng)用中幾乎不用。但是至少要了解，并會(huì)由遞推式計(jì)算通項(xiàng)式。 特征方程：特征方程可以理解為求通項(xiàng)公式的一個(gè)工具。 
2.矩陣乘法
這里貼一下P1962的代碼 #include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n;
const LL mod=1000000007;
struct matrix{
LL a[5][5];
}ans;//矩陣
void print(matrix a)
{
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
printf('%lld ',a.a[i][j]);
printf('\n');
}
}//打印矩陣
matrix init()
{
matrix ret;
ret.a[1][1]=1,ret.a[1][2]=1;
ret.a[2][1]=1,ret.a[2][2]=0;
return ret;
}//遞推矩陣
matrix mul(matrix a,matrix b)
{
matrix ret;
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
ret.a[i][j]=0;
for(int k=1;k<=2;k++)
ret.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod,ret.a[i][j]%=mod;
}
}
//print(ret);
return ret;
}//矩陣相乘
matrix fast_power(matrix a,LL x)
{
matrix ret;
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
if(i==j)ret.a[i][j]=1;
else ret.a[i][j]=0;
}
}//初始矩陣
while(x)
{
if(x&1)ret=mul(ret,a);
a=mul(a,a);
x>>=1;
}
return ret;
}//矩陣快速冪
int main()
{
scanf('%lld',&n);
ans=fast_power(init(),n-1);
printf('%lld\n',ans.a[1][1]);
return 0;
}
3.斐波那契數(shù)列的一個(gè)性質(zhì)
證明2： 采用數(shù)學(xué)歸納法 設(shè)1至2*n都滿足上述公式 （兩個(gè)公式同時(shí)滿足） 
所以原命題成立
證明3： 
那怎么證明上面這個(gè)式子呢？ 還是可以通過數(shù)學(xué)歸納法（只是這里提供了一個(gè)新的思路，后期也要用到這個(gè)定理） 
所以原命題成立 利用減半遞推+記憶化，便可以AC 代碼： #pragma GCC diagnostic error '-std=c++14'
#pragma GCC target('avx')
#pragma GCC optimize(3)
#pragma GCC optimize('Ofast')//強(qiáng)行優(yōu)化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
const ll mod=1e9+7;
map<ll,ll>f;
ll solve(ll x)
{
if(x==0)return 0;
if(x==1)return 1;
if(x==2)return 1;//邊界條件
ll y=(x>>1),f1=f[y-1]?f[y-1]:solve(y-1),f2=f[y]?f[y]:solve(y),f3=f[y+1]?f[y+1]:solve(y+1);//處理f[y-1],f[y],f[y+1]
if(x&1)return (f[x]=(f3*f3+f2*f2+mod)%mod);//如果為奇數(shù)
else return (f[x]=(f3*f3-f1*f1+mod)%mod);//如果為偶數(shù)
//套用公式+記憶化，把答案丟進(jìn)map里
}
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0') { if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
scanf('%lld',&n);
printf('%lld\n',(solve(n)+mod)%mod);//瘋狂取模
return 0;
}
4.另外一個(gè)性質(zhì)我們先來看一道題目 P1306 斐波那契公約數(shù) 題目描述：
5.又一個(gè)性質(zhì)
6.線段樹眾所周知，線段樹可以處理很多關(guān)于區(qū)間的問題 （如果對線段樹沒有了解的，推薦洛谷日報(bào)淺談線段樹或者我的博客線段樹1，線段樹2，線段樹3）
這是關(guān)于數(shù)列操作的一個(gè)表格。 注意到13操作：區(qū)間加斐波那契數(shù)列 這就是我們接下來要研究的 例題： CF446C 題意翻譯:
代碼： #include<bits/stdc++.h>
#define rd(x) x=read()
#define N 300005
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
typedef long long ll;
ll n,m;
struct T{
ll f1,f2,v;
}t[N*20];
ll a[N],f[N],sum[N];
const ll mod=1e9+9;
inline ll read()
{
ll f=1,x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
void init()
{
f[1]=1,f[2]=1;
for(ll i=3;i<=n+1;i++)f[i]=(f[i-2]+f[i-1])%mod;
}//預(yù)處理斐波那契
void pushup(ll rt,ll pos)
{
t[rt].f1%=mod,t[rt].f2%=mod;
t[rt].v=t[ls].v+t[rs].v+(t[rt].f1*f[pos]+t[rt].f2*f[pos+1]-t[rt].f2),t[rt].v%=mod;
}//更新rt
void pushdown(ll rt,ll l,ll r)
{
if(t[rt].f1==0&&t[rt].f2==0)return ;
ll mid=(l+r)>>1;
t[ls].f1+=t[rt].f1,t[rs].f1+=t[rt].f1*f[mid-l]+t[rt].f2*f[mid-l+1];
t[ls].f2+=t[rt].f2,t[rs].f2+=t[rt].f1*f[mid-l+1]+t[rt].f2*f[mid-l+2];
t[rt].f1=t[rt].f2=0;
pushup(ls,mid-l+1),pushup(rs,r-mid);
} //標(biāo)記下傳
void update(ll rt,ll l,ll r,ll L,ll R)
{
if(L<=l&&r<=R)//邊界條件
{
t[rt].f1+=f[l-L+1];
t[rt].f2+=f[l-L+2];
t[rt].f1%=mod,t[rt].f2%=mod;
pushup(rt,r-l+1);
return ;
}
pushdown(rt,l,r);
ll mid=(l+r)>>1;
if(L<=mid)update(ls,l,mid,L,R);
if(mid<R)update(rs,mid+1,r,L,R);
pushup(rt,r-l+1);
}//區(qū)間加斐波那契數(shù)列
ll query(ll rt,ll l,ll r,ll L,ll R)
{
if(L<=l&&r<=R)return t[rt].v;
pushdown(rt,l,r);
ll res=0;
ll mid=(l+r)>>1;
if(L<=mid)res+=query(ls,l,mid,L,R);
if(mid<R)res+=query(rs,mid+1,r,L,R);
return res%mod;
}//查詢和
int main()
{
rd(n),rd(m);
init();
for(ll i=1;i<=n;i++)rd(a[i]),sum[i]=sum[i-1]+a[i];//預(yù)處理前綴和
while(m--)
{
ll opt,l,r;
rd(opt),rd(l),rd(r);
if(opt==1)update(1,1,n,l,r);
else printf('%lld\n',(query(1,1,n,l,r)+sum[r]-sum[l-1]+mod)%mod);
}
return 0;
}
參考文獻(xiàn)衷心的感謝以上的文獻(xiàn)
|
