关于斐波那契数列

· · 个人记录

FZQOJ 博客链接。

博客园链接。

关于斐波那契数列

警告：本文使用了微少的 \LaTeX，请谨慎食用。

斐波那契数列的定义

F(n)=\begin{cases}0&n=0\\1&n=1\\F(n-1)+F(n-2)&n \ge 2\end{cases}

这个是很显然的吧。

例题

P1720 月落乌啼算钱（斐波那契数列）

这一道题是语法的入门题，由于项数不超过 33，我们可以直接使用递推公式。

#include<cstdio>
int main(){
    int n,n1=1,n2=1,s=0;//第一项和第二项。
    scanf("%d",&n);
    if (n==1) return printf("%d\n",n1),0;
    s=n2;
    for (int i=3;i<n;i++){
        if (i&1) n1+=n2,s=n1;
        else n2+=n1,s=n2;
    } 
    printf("%d\n",s);
    return 0;
}

上面的代码时间复杂度是 O(n) 的，但是，斐波那契数列是有公式的！我们不能只止步于递推。

公式：

F(n)=\dfrac{1}{\sqrt5}\left[(\dfrac{1+\sqrt5}{2})^n-(\dfrac{1-\sqrt5}{2})^n\right]

证明（虽然我也没看懂）：

于是我们就可以利用上面的通项公式，使用 cmath 库中的 sqrt 和 pow 函数来简洁地求解：

//the code is from chenjh
#include<cstdio>
#include<cmath>
int main(){
    int n;scanf("%d",&n);
    printf("%.2lf\n",1.0/sqrt(5)*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n)));
    return 0;
}

上面的代码的时间复杂度是 O(1) 的！（我们可以暂且认为 sqrt 和 pow 函数的时间复杂度 O(1) 的）

「POJ3070」Fibonacci

此题要求 F_n (0 \le n \le 10^9)，普通的 O(n) 递推一定是无法胜任的。

所以我们就需要——矩阵乘法来加速递推。

斐波那契数列的另外一个通项公式是：

\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{matrix}\underbrace{\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}1&1\\1&0\end{bmatrix}\dots\begin{bmatrix}1&1\\1&0\end{bmatrix}}\\{n \text{ times}}\end{matrix}

于是我们就可以利用矩阵乘法配合快速幂进行 O(2^3 \log n) 复杂度的递推，其中 2^3 为矩阵乘法所需要的复杂度。

//the code is from chenjh
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int m=10000;
void mul(int f[2],int a[2][2]){
    int c[2];
    memset(c,0,sizeof(c));
    for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
            c[j]=(c[j]+(LL)f[k]*a[k][j])%m;
    memcpy(f,c,sizeof(c));
}
void mulself(int a[2][2]){
    int c[2][2];
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+(LL)a[i][k]*a[k][j])%m;
    memcpy(a,c,sizeof(c));
}
int main(){
    int n;
    while(cin>>n && n!=-1){
        int f[2]={0,1};
        int a[2][2]={{0,1},{1,1}};
        for(;n;n>>=1){
            if(n&1) mul(f,a);
            mulself(a);
        }
        cout<<f[0]<<endl;
    }
    return 0;
}

LibreOJ #10221. 「一本通 6.5 例 3」Fibonacci 前 n 项和

设斐波那契数列的第 n 项为 F_n，前 n 项和为 S_n。

方法一

根据矩阵乘法的定义，可以列出公式：

\begin{bmatrix}S_n&F_n&F_{n+1}\end{bmatrix}=\begin{bmatrix}S_{n-1}&F_{n-1}&F_n\end{bmatrix} \times \begin{bmatrix}1&0&0\\0&0&1\\1&1&1\end{bmatrix}

最后利用矩阵乘法配合快速幂实现，时间复杂度为 O(3^3 \log n)。

//the code is from chenjh
#include<cstdio>
#include<cstring>
typedef long long LL;
LL m;
void mul(LL f[3],LL a[3][3]){
    LL c[3];
    memset(c,0,sizeof(c));
    for(int j=0;j<3;j++)
        for(int k=0;k<3;k++)
            c[j]=(c[j]+f[k]*a[k][j])%m;
    memcpy(f,c,sizeof(c));
}
void mulself(LL a[3][3]){
    LL c[3][3];
    memset(c,0,sizeof(c));
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                c[i][j]=(c[i][j]+a[i][k]*a[k][j])%m;
    memcpy(a,c,sizeof(c));
}
int main(){
    LL n;
    scanf("%lld%lld",&n,&m);
    LL f[3]={0,0,1};
    LL a[3][3]={{1,0,0},{0,0,1},{1,1,1}};
    for(;n;n>>=1){
        if(n&1) mul(f,a);
        mulself(a);
    }
    printf("%lld\n",f[0]);
    return 0;
}

方法二

公式：

S_n=F_{n+2}-1

证明：

运用数学归纳法。

当 n=1 时，命题成立。

假设 n=k 时，命题成立。

当 n=k+1 时：

\begin{aligned}F_{k+3}-1 &= F_{k+1}+F_{k+2}-1\\&= F_{k+1}+\sum\limits_{i=1}^kF_i\\&=\sum\limits_{i=1}^{k+1}F_i\end{aligned}

所以直接用矩阵乘法配合快速幂求出 F_{n+2} 即可。

时间复杂度 O(2^3 \log n)。

//the code is from chenjh
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL m;
void mul(LL f[2],LL a[2][2]){
    LL c[2];
    memset(c,0,sizeof(c));
    for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
            c[j]=(c[j]+f[k]*a[k][j])%m;
    memcpy(f,c,sizeof(c));
}
void mulself(LL a[2][2]){
    LL c[2][2];
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[i][j]=(c[i][j]+a[i][k]*a[k][j])%m;
    memcpy(a,c,sizeof(c));
}
int main(){
    LL n;
    scanf("%lld%lld",&n,&m);
    n+=2;
    LL f[2]={0,1};
    LL a[2][2]={{0,1},{1,1}};
    for(;n;n>>=1){
        if(n&1) mul(f,a);
        mulself(a);
    }
    printf("%lld\n",f[0]-1);
    return 0;
}

LibreOJ #10222. 「一本通 6.5 例 4」佳佳的 Fibonacci

计算出前 n 项，输入到 OEIS 中，你会发现就是 A014286 号数列。

通项公式是：

S(n)=n \times F_{n+2} - F_{n+3} +2

于是就可以直接计算了，但是我们仍要证明一下：

把他变成一个三角形：

\begin{matrix}F_1&&&&\\F_2&F_2&&&\\F_3&F_3&F_3&&&\\F_4&F_4&F_4&F_4&&\\F_5&F_5&F_5&F_5&F_5\end{matrix} \dots

答案就是这个三角形内所有数之和。

我们可以把这个三角形竖着看，发现了啥？这个式子就是：

\sum \limits_{i=1}^n (S_n-S_{i-1})

把 S_n 提取出来：

nS_n-\sum\limits_{i=1}^nS_{i-1}

这个时候，S_n=F_{n+2}-1 派上用场了。把这个式子往里面套啊！

n(F_{n+2}-1) - \sum\limits_{i=1}^n (F_{i+1}-1)

发现了啥？\sum\limits_{i=1}^n (F_{i+1}-1) 其实也可以转化为 S_{n+1}-F_1-n。

把 S_n=F_{n+2}-1 再往 S_{n+1} 里面套！

答案就变成了：

n(F_{n+2}-1)- (F_{n+3}-1-F_1-n) =nF_{n+2}-n-F_{n+3}+1+F_1+n =nF_{n+2}-F_{n+3}+2 
//the code is from chenjh
#include<cstdio>
#include<cstring>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
typedef long long LL;
int n,m;
void mul(int f[2],int a[2][2]){
    int c[2];
    memset(c,0,sizeof c);
    rep(i,0,2)rep(j,0,2)c[i]=(c[i]+(LL)f[j]*a[j][i])%m;
    memcpy(f,c,sizeof c);
}
void mulself(int a[2][2]){
    int c[2][2];
    memset(c,0,sizeof c);
    rep(i,0,2)rep(j,0,2)rep(k,0,2)c[i][j]=(c[i][j]+(LL)a[i][k]*a[k][j])%m;
    memcpy(a,c,sizeof c);
}
int main(){
    scanf("%d%d",&n,&m);
    int f[2]={0,1};
    int a[2][2]={{0,1},{1,1}};
    for(int x=n+2;x;x>>=1,mulself(a))if(x&1)mul(f,a);
    printf("%lld\n",((LL)n*f[0]-f[1]+2+m)%m);
    return 0;
}

补充知识

  1. fib在模m后，一定存在周期性。
  2. More：斐波那契数列的性质 - Milkor - 博客园 (cnblogs.com)

参考文献

本人制作不易，公式可能会有打错的地方，欢迎指出错误，点个赞吧。