斐波那契数列

斐波那契数列是一个很神奇的东西,今天我们就来谈一谈它。

前言:本篇博客中会有大量的公式,每一个公式都会给出严谨的证明(证明方法都是最严谨的数学归纳法

1.从特征方程说起

前言:事实上,特征方程所求得的通项公式在实际应用中几乎不用。但是至少要了解,并会由递推式计算通项式。

特征方程:特征方程可以理解为求通项公式的一个工具。


对于一阶递推式,形如:$f[i]=p*f[i-1]+x$

设$q$,满足$f[i]+q=p(f[i-1]+q)$

展开得到$f[i]=p*f[i-1]+q*(p-1)$

$\therefore$ $x=q*(p-1)$

$q=\frac{x}{p-1}$

令$g[i]=f[i]+q$

易知{$g[i]$}为等比数列,公比为$p$

所以$g[i]=(f[1]+q)*p^{i-1}$

$f[i]=(f[1]+\frac{x}{p-1})*p^{i-1}-\frac{x}{p-1}$


对于二阶递推式,形如:$f[i]=p*f[i-1]+q*f[i-2]$

设$u,v$,满足$f[i]-u*f[i-1]=v*(f[i-1]-u*f[i-2])$

$f[i]=(u+v)*f[i-1]+u*v*f[i-2]$

展开得到$q=-u*v$

$u^{2}=p*u+q$

这就是特征方程。


可以看到{$f[i]-u*f[i-1]$}是一个公比为v的等比数列

$\frac{f[i]-u*f[i-1]}{f[i-1]-u*f[i-2]}=v$

设$f[1]-u*f[0]=a$

$f[2]-u*f[1]=a*v$

……

$f[n]-u*f[n-1]=a*v^{n-1}$

通过计算得到

$f[n]-u^{n}*f[0]=a*\sum^{n}_{i=1}(u^{n-1}*(\frac{v}{u})^{i-1})$

对于$u,v$的大小关系分两类讨论,就可以得到:

当两根不相同时,$f[n]$可以表示成$A*u^{n}+B*v^{n}$的形式


我们对于斐波那契数列递推式进行一遍上述操作

注意:这里是广义的斐波那契数列

即:$a[1]=m,a[2]=k,a[n]=p*a[n-1]+q*a[n-2]$

注:$p^2+4*q>0,p,q\neq0,n>2$

令$a[n]=A*\alpha^{n}+B*\beta^{n}$

其中有$\alpha,\beta$为方程$x^{2}=p*x+q$(特征方程)的两根

前文保证($p^{2}+4*q>0$,即$\Delta>0$)

不妨设$\alpha=\frac{p-\sqrt{p^{2}+4*q}}{2}$

$\beta=\frac{p+\sqrt{p^{2}+4*q}}{2}$

所以$a[n]=A*\alpha^{n}+B*\beta^{n}=A*(\frac{p-\sqrt{p^{2}+4*q}}{2})^{n}+B*(\frac{p+\sqrt{p^{2}+4*q}}{2})^{n}$

上式对$a[1],a[2]$同样成立

将$a[1],a[2]$代入得

$m=\frac{p-\sqrt{p^{2}+4*q}}{2}*A+\frac{p+\sqrt{p^{2}+4*q}}{2}*B$

$k=(\frac{p-\sqrt{p^{2}+4*q}}{2})^{2}*A+(\frac{p+\sqrt{p^{2}+4*q}}{2})^{2}*B$

令$\sqrt{p^{2}+4*q}=y$,则原方程为

$m=\frac{p-y}{2}*A+\frac{p+y}{2}*B$

$k=(\frac{p-y}{2})^{2}*A+(\frac{p+y}{2})^{2}*B$

令$\frac{p-y}{2}=s,\frac{p+y}{2}=t,s+t=p,t-s=y$

$m=s*A+t*B$

$k=s^{2}*A+t^{2}*B$

$A=\frac{(p+y)*m-2*k}{(p-y)*y}$

$B=\frac{2*k-(p-y)*m}{(p+y)*y}$

所以$a[n]=\frac{(p+y)*m-2*k}{(p-y)*y}*(\frac{p-y}{2})^{n}+\frac{2*k-(p-y)*m}{(p+y)*y}*(\frac{p+y}{2})^{n}$


读者可以把$m=k=p=q=1$代入上式,就可以得到斐波那契的通项公式

$f[n]=\frac{1}{\sqrt{5}}*[(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]$

当$p^{2}-4*q<=0$时,读者可以自行思考一下,通项公式又会变成什么样


2.矩阵乘法

在具体实现中,如果题目要求数据范围过大,特征方程所求的通项公式不容易实现,暴力递推会TLE。

因此,我们采用矩阵乘法。

由于$f[i]=f[i-1]+f[i-2]$是一个很简单的递推式,它的矩阵也很简单

$\begin{bmatrix}1&1\\1&0\end{bmatrix}$

关于矩阵乘法的其他内容本文不再阐述,推荐洛谷日报:从零开始的矩阵乘法

时间复杂度:$O(log(n))$

模板题:P1962 斐波那契数列

这是一道关于斐波那契数列的模板题

观察数据范围得到,朴素的O(n)算法显然会TLE。显然用矩阵乘法。

同理,P1349也是同样的方法,但是递推矩阵不一样

$\begin{bmatrix}p&1\\q&0\end{bmatrix}$


这里贴一下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.斐波那契数列的一个性质

同时,我们可以采用另外一种做法:

$f[2*n]=f[n+1]^{2}-f[n-1]^{2}=(2*f[n-1]+f[n])*f[n]$

$f[2*n+1]=f[n+1]^{2}+f[n]^{2}$

在这里,我们证明一下这两个定理。

证明1:

直接采用通项公式(通项公式还是有用的)

设$s=\frac{1+\sqrt{5}}{2},t=\frac{1-\sqrt{5}}{2}$

引理:

$s^{n}-t^{n}=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n}}$

把$(1+\sqrt{5})^{n}$和$(1-\sqrt{5})^{n}$进行多项式展开

……

这样的证明过于繁琐,读者可以亲自尝试一下。


证明2:

采用数学归纳法

设$1$至$2*n$都满足上述公式 (两个公式同时满足)

$f[2*n+1]=f[2*n]+f[2*n-1]=f[n+1]^{2}-f[n-1]^{2}+f[n]^{2}+f[n-1]^{2}=f[n+1]^{2}+f[n]^{2}$

$f[2*n+2]=f[2*n+1]+f[2*n]$

$=f[n+1]^{2}+f[n]^{2}+f[n+1]^{2}-f[n-1]^{2}$

$=f[n+1]^{2}+f[n+1]^{2}+f[n]^{2}-f[n-1]^{2}$

$=f[n+1]^{2}+f[n+1]^{2}-2*f[n+1]*f[n]+f[n]^{2}-f[n-1]^{2}+2*f[n+1]*f[n]$

$=f[n+1]^{2}+f[n-1]^{2}-f[n-1]^{2}+2*f[n+1]*f[n]$

$=f[n+1]^{2}+2*f[n+1]*f[n]$

$=f[n+1]*(2*f[n]+f[n+1])$

$=f[n+2]^{2}-f[n]^{2}$

所以原命题成立


证明3:

$f[2*n]=f[n+1]^{2}-f[n-1]^{2}$

$f[2*n+1]=f[n+1]^{2}+f[n]^{2}$

只需证明:

$f[n+m]=f[m-1]*f[n]+f[m]*f[n+1]$

若上式成立

$f[2*n]=f[n+n]$

$=f[n-1]*f[n]+f[n]*f[n+1]$

$=f[n]*(f[n+1]+f[n-1])$

$=f[n+1]^{2}-f[n-1]^{2}$

$f[2*n+1]=f[n+(n+1)]$

$=f[n-1]*f[n+1]+f[n]*f[n+2]$

$=f[n+1]^{2}-f[n]*f[n+1]+f[n]^2+f[n]*f[n+1]$

$=f[n+1]^{2}+f[n]^{2}$

那怎么证明上面这个式子呢?

还是可以通过数学归纳法(只是这里提供了一个新的思路,后期也要用到这个定理)

设$1$至$x-1$都两两满足$f[n+m]=f[m-1]*f[n]+f[m]*f[n+1]$

下证

$f[1+x]=f[x-1]*f[1]+f[x]*f[2]$

$f[2+x]=f[x-1]*f[2]+f[x]*f[3]$

$……$

$f[x-1+x]=f[x-1]*f[x-1]+f[x]*f[x]$

对于任意的$f[p+x]$

都有$f[p+x]=f[(p-1)+x]+f[(p-2)+x]$

$=f[p+(x-1)]+f[(p-1)+(x-1)]$

$=f[x-2]*f[p]+f[x-1]*f[p+1]+f[x-2]*f[p-1]+f[x-1]*f[p]$

$=f[x-2]*f[p+1]+f[x-1]*f[p+2]$

$=f[x]*f[p+1]-f[x-1]*f[p+1]+f[x-1]*f[p]+f[x-1]*f[p+1]$

$=f[x]*f[p+1]+f[x-1]*f[p]$

所以原命题成立

利用减半递推+记忆化,便可以AC

代码:

#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")//强行优化

#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);//如果为奇数
    else return (f[x]=(f3*f3-f1*f1+mod)%mod);//如果为偶数
   //套用公式+记忆化,把答案丢进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;
}

时间复杂度:递归$O(log(n))$,map$O(log(n))$总时间复杂度为$O(log^{2}(n))$

这里提到了这两个公式,顺便再拓展一个:

$f[3*n]=f[n+1]^{3}+f[n]^{3}-f[n-1]^{3}$

有兴趣的读者可以亲自证明一下。

当然啦,它对应的也有两个公式。

上述的数学归纳法的证明必须有几个公式互相依靠。


4.另外一个性质

我们先来看一道题目

P1306 斐波那契公约数

题目描述:

对于$Fibonacci$数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~

但是现在有一个很“简单”问题:第$n$项和第$m$项的最大公约数是多少?($n\leqslant1e9$)

本题要求$gcd(f[n],f[m])$

我们可以用矩阵乘法把$f[n],f[m]$都算出来

题目要求对1e8取模,所以做gcd的时候就会遇到问题。

斐波那契数列中还有一个性质:

$gcd(f[n],f[m])=f[gcd(n,m)]$

证明:

若证$gcd(f[n],f[m])=f[gcd(n,m)]$

即证$gcd(f[n+m],f[n])=gcd(f[m],f[n])$

$gcd(f[n+m],f[n])$

$=gcd(f[n+1]f[m]+f[n]f[m-1],f[n])$

$=gcd(f[n+1]f[m],f[n])$

$=gcd(f[n+1],f[n])*gcd(f[m],f[n])$

$=gcd(f[m],f[n])$

得证

有了这个性质之后

题目$<==>$求$f[gcd(n,m)] mod 1e8$

矩阵乘法即可


5.又一个性质

先看一道题P3986

题目描述:

定义一个数列:

$f(0) = a, f(1) = b, f(n) = f(n - 1) + f(n - 2)$

其中$ a, b $均为正整数,$n≥2$。

问有多少种 $(a, b)$,使得$k$出现在这个数列里,且不是前两项。

由于答案可能很大,你只需要输出答案模$10^{9}+7$的结果即可。

数据范围:

$1≤k≤10^{9}$

简单分析得:

设$g[0]=1,g[1]=1,g[n]=g[n-1]+g[n-2](n≥2)$(就是斐波那契数列)

显然有$f[n]=g[n-1]*a+g[n-2]*b(n≥2)$

问$f[n]=k$的情况数

由于$1≤k≤10^{9}$,所以$n$的取值范围也很小,只要暴力枚举$g[n-1],g[n-2]$,然后对于每一种情况用$exgcd$解一个不定方程即可


这里介绍另一种方法

先介绍一个性质

$f[i]f[i-1]-f[i+1]f[i-2]=(-1)^{i}$$(f[0]=0,f[-1]=1)$

还是用数学归纳法

另$g[i]=f[i]f[i-1]-f[i+1]f[i-2]$

当$i=0$时,原式显然成立

$g[i]=(f[i-1]+f[i-2])f[i-1]-(f[i]+f[i-1])f[i-2]$$=f[i-1]^{2}-f[i]f[i-2]$

设$i=k$时,原命题成立

$g[k]=f[k-1]^{2}-f[k]f[k-2]$

$g[k+1]=f[k]^{2}-f[k+1]f[k-1]$

$g[k]+g[k+1]=0$

$\because g[k]=-1^{k}$

$\therefore g[k+1]=-1^{k+1}$

两式相加得0

所以原命题成立

根据上式

方程$g[n-1]*a+g[n-2]*b=k$就有通解$x=k*-1^{n-2}f[n-3]$

求得一个解之后,其余的就好求了


6.线段树

众所周知,线段树可以处理很多关于区间的问题

(如果对线段树没有了解的,推荐洛谷日报浅谈线段树或者我的博客线段树1线段树2线段树3

数列操作

这是关于数列操作的一个表格。

注意到13操作:区间加斐波那契数列

这就是我们接下来要研究的

例题:

CF446C

题意翻译:

题面大意:给出一个数列,每次可以选取一个区间,按顺序加上第$i$个$Fibonacci Numbers$(斐波那契数)进行更新,也可以查询某一个区间的总和。

这题虽然是黑题,其实并不难

我们只要思考几件事:

1.线段树的标记下传($pushdown$)能不能在$O(1)$内完成

2.线段树更新$sum$能不能在$O(1)$内完成

对于1,前文提到$f[n]=g[n-1]*a+g[n-2]*b$

对于2,这里再提一个性质:

令$s[i]=\sum_{i=1}^{n}f[i]$

$s[i]=f[n+2]-f[2]$

这个定理的证明

还是用数学归纳法。。。

显然当$i=1$时,原命题成立

设$i=k$时,原命题成立。

$s[k+1]=s[k]+f[k+1]=f[k+2]-f[2]+f[k+1]=f[k+3]-f[2]$

$\therefore$ 原命题成立

便能实现再$O(1)$内完成更新$sum$了

代码:

#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;
}//预处理斐波那契

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); 
} //标记下传

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);
}//区间加斐波那契数列

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];//预处理前缀和
    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;
}

7.$\sum_{i=1}^{n}f[i]*i$

$\sum_{i=1}^{n}f[i]*i=n*f[n+2]-f[n+3]+2$

命运驱使着我用数学归纳法。。。

当$n=1$时,原命题显然成立

设$n=k$时,原命题成立

令$s[i]=\sum_{i=1}^{n}f[i]*i$

$s[k+1]=s[k]+f[k+1]*(k+1)$

$=k*f[k+2]-f[k+3]+2+f[k+1]*(k+1)$

$=k*f[k+3]-f[k+3]+2+f[k+1]$

$=k*f[k+3]-f[k+2]+2$

所以原命题成立

然后用矩阵乘法计算即可。


参考文献

衷心的感谢以上的文献

推荐文献

完结撒花!


后记:

在翻阅洛谷日报的时候,我发现很多的算法都已经介绍了,

唯独没有神奇的斐波那契数列,于是心血来潮,写下了这篇文章。


发表于 2019-05-02 11:40:52 in math