时间戳

首页 > 技术文章 > 「算法笔记」斐波那契数列

「算法笔记」斐波那契数列

maoyiting 2020-11-14 08:43 原文

一、定义

斐波那契数列是满足如下性质的一个数列：

\(F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.\)

有通项公式：

\(\displaystyle F_n=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right]\)

快速求斐波那契数列的第 \(n\) 项：矩阵快速幂 优化。

值得注意的一点是 \(5\) 在模 \(998244353,10^9+7\) 时都没有二次剩余，但在模 \(10^9+9\) 意义下有二次剩余，为 \(383008016\)，所以在组合题中看到斐波那契数列与 \(10^9+9\) 一般是套通项公式了。

二、性质

1. 求和性质

  • 直接求和：\(F_1+F_2+\cdots+F_n=F_{n+2}-1\)。

    • 证明：\(\sum_{i=1}^n F_i=\sum_{i=1}^n {F_{i+2}-F_{i+1}}=F_{n+2}-F_2=F_{n+2}-1\)。

  • 奇数项求和：\(F_1+F_3+F_5+F_7+\cdots+F_{2n-1}=F_{2n}\)。

    • 证明：\(F_1+F_3+F_5+F_7+\cdots+F_{2n-1}\)\(=F_1+(F_1+F_2)+(F_3+F_4)+(F_5+F_6)+\cdots+(F_{2n-3}+F_{2n-2})\)\(=F_1+\sum_{i=1}^{2n-2}F_i=F_1+(F_{2n}-1)=F_{2n}\)。

  • 偶数项求和：\(F_2+F_4+F_6+F_8+\cdots+F_{2n}=F_{2n+1}-1\)。

    • 证明：\(F_2+F_4+F_6+F_8+\cdots+F_{2n}\)\(=F_2+(F_2+F_3)+(F_4+F_5)+(F_6+F_7)+\cdots+(F_{2n-2}+F_{2n-1})\)\(=F_2+\sum_{i=1}^{2n-1}F_i-F_1=F_{2n+1}-1\)。

  • 平方求和：\(F_1^2+F_2^2+F_3^2+F_4^2+\cdots+F_n^2=F_n\cdot F_{n+1}\)。

    • 证明：归纳法。显然对于 \(n=1\) 结论成立。假设有 \(\sum_{i=1}^{n-1} F_i^2=F_{n-1}F_n\) 成立，那么 \(\sum_{i=1}^n F_i^2=F_{n-1}F_n+F_n^2=F_nF_{n+1}\)。（也可以尝试 画图证明。以 \(F_i\) 作为正方形的边长。）

2. 一些等式

  • 卡西尼恒等式（Cassini's identity）：\(F_{n-1}F_{n+1}-F_n^2=(-1)^n\)。

  • 附加性质：\(F_{n+m}=F_mF_{n+1}+F_{m-1}F_n\)。注意到将 \(m=n\) 代入原式可以得到另一性质：\(F_{2n}=F_n(F_{n-1}+F_{n+1})\)。

    • 证明：对 \(n\) 进行归纳法。当 \(n=1\) 时，\(F_{m+1}=F_mF_2+F_{m-1}F_1=F_m+F_{m-1}\)，结论成立。

    • 假设有 \(F_{(n-1)+m}=F_mF_{(n-1)+1}+F_{m-1}F_{n-1}\) 成立。则 \(F_{n+m}=F_{(n-1)+(m+1)}=F_{m+1}F_{(n-1)+1}+F_{(m+1)-1}F_{n-1}\)\(=(F_{m-1}+F_m)F_n+F_mF_{n-1}=F_{m-1}F_n+F_m(F_n+F_{n-1})=F_{m-1}F_n+F_mF_{n+1}\)。

3. 最大公约数相关

  • 相邻项性质：\(\gcd(F_n,F_{n+1})=1\)。

    • 证明：归纳法。显然对于 \(n=1\) 结论成立。假设有 \(\gcd(F_{n-1},F_n)=1\) 成立，那么：\(\gcd(F_n,F_{n+1})=\gcd(F_n,F{n+1}-F_n)=\gcd(F_n,F_{n-1})=1\)。

  • 最大公约数性质：\(\gcd(F_n,F_m)=F_{\gcd(n,m)}\)。

    • 证明：不妨设 \(n<m\)，根据附加性质，\(\gcd(F_n,F_m)=\gcd(F_n,F_{n+(m-n)})=\gcd(F_n,F_{m-n}F_{n+1}+F_{m-n-1}F_n)\)\(=\gcd(F_n,F_{m-n}F_{n+1})\)。

    • 由相邻项性质可知 \(\gcd(F_n,F_{n+1})=1\)，所以 \(\gcd(F_n,F_m)=\gcd(F_n,F_{m-n}F_{n+1})=\gcd(F_n,F_{m-n})\)。

    • 递归下去就是辗转相减法。最终会得到的形式应当就是 \(\gcd(F_n,F_m)=F_{\gcd(n,m)}\)。

  • 其他性质：\(n\mid m⇔F_n\mid F_m\)。

    • 证明：当 \(n\mid m\) 时，\(\gcd(F_n,F_m)=F_{\gcd(n,m)}=F_n\)，所以 \(F_n\mid F_m\)。

4. 项与项之间的关系

  • 平方与前后项：\(F_n^2-F_{n-1}\cdot F_{n+1}=(-1)^{n-1}\)。

  • 隔项关系：\(F_{2n-2m-2}(F_{2n}+F_{2n+2})=F_{2m+2}+F_{4n-2m}\)（\(n>m\geq -1,n\geq 1\)）。

  • 两倍项关系：\(\dfrac{F_{2n}}{F_n}=F_{n-1}+F_{n+1}\)。

三、模意义下周期性

在模 \(p\) 意义下，斐波那契的第 \(n+1\) 项 \(F_{n+1}\) 仅取决于 \((F_{n−1}\bmod p,F_n\bmod p)\)。这个二元组有 \(p^2\) 种取值。

\(p\) 的剩余系大小为 \(p\)，意味着在前 \(p^2+1\) 个二元组中必有两个相同的数对。于是这两个二元组往后生成相同的斐波那契数列，那么它们就是有周期性的。

所以斐波那契数列在模意义下一定会产生循环节，并且一定是纯循环的。

事实上，有一个远比它强的结论：形如 \(n=2\times 5^k\) 的循环节均为 \(6n\)，并且可以证明斐波那契数列模 \(n\) 意义下的最小循环节不超过 \(6n\)。详见 此处。

四、例题

1. SPOJ FIBOSUM - Fibonacci Sum

题目大意：求 \(\sum_{i=n}^m F_i\) 对 \(10^9+7\) 取模的值。其中 \(F_i\) 表示斐波那契数列第 \(i\) 项的值。\(T\leq 1000,0\leq n\leq m\leq 10^9\)。

Solution：

根据性质 \(F_1+F_2+\cdots+F_n=F_{n+2}-1\) 可得：

\(\sum_{i=n}^m F_i=\sum_{i=1}^m F_i-\sum_{i=1}^{n-1} F_i=(F_{m+2}-1)-(F_{n+1}-1)=F_{m+2}-F_{n+1}\)

矩阵快速幂优化即可。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2,mod=1e9+7;
int t,n,m,f[N][N];
void mul(int x[N][N],int y[N][N]){
    int c[N][N];
    memset(c,0,sizeof(c));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                c[i][j]=(c[i][j]+x[i][k]*y[k][j])%mod;
    memcpy(x,c,sizeof(c));
}
int query(int n){    //求斐波那契数列第 n 项的值 
    int a[N][N]={{0,1},{1,1}};
    memset(f,0,sizeof(f)),n++;
    for(int i=0;i<N;i++) f[i][i]=1;
    for(;n;n>>=1,mul(a,a))
        if(n&1) mul(f,a);
    return f[0][0];
} 
signed main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",(query(m+2)-query(n+1)+mod)%mod);
    }
    return 0;
}

2. CF226C Anniversary

题目大意：给定 \(m,l,r,k\)。在 \([l,r]\) 中选出 \(k\) 个数 \(a_1,a_2,\cdots,a_k\)，使得 \(\gcd(F_{a_1},F_{a_2},\cdots,F_{a_k})\) 尽可能大。求对 \(m\) 取模后的结果。

Solution：

根据性质 \(\gcd(F_n,F_m)=F_{\gcd(n,m)}\) 可得：\(\gcd(F_{a_1},F_{a_2},\cdots,F_{a_k})=F_{\gcd(a_1,a_2,\cdots,a_k)}\)。

由于 \(F_n=F_{n-1}+F_{n-2}>F_{n-1}\)，所以 \(\gcd(a_1,a_2,\cdots,a_k)\) 的值越大越好。

问题转化为在 \([l,r]\) 中选 \(k\) 个数，使得这 \(k\) 个数的 \(\gcd\) 最大。

在一个区间 \([l,r]\) 中，含有因子 \(x\) 的数的数量为 \(\frac{r}{x}-\frac{l-1}{x}\)。

令 \(calc(x)=\frac{r}{x}-\frac{l-1}{x}\)。枚举 \(1\leq i\leq \sqrt{r}\)，判断 \(calc(i)\) 和 \(calc(\frac{r}{i})\) 是否大于等于 \(k\)。记录最大的满足 \(calc(x)\geq k\) 的 \(x\)。

 \(x\) 即为最大的 \(\gcd(a_1,a_2,\cdots,a_k)\) 的值。答案即为 \(F_x\)。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2;
int l,r,mod,k,f[N][N],res;
int calc(int x){    //求区间 [l,r] 中，含有因子 x 的数的数量 
    return r/x-(l-1)/x;
}
void mul(int x[N][N],int y[N][N]){
    int c[N][N];
    memset(c,0,sizeof(c));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                c[i][j]=(c[i][j]+x[i][k]*y[k][j])%mod;
    memcpy(x,c,sizeof(c));
}
int query(int n){    //求斐波那契数列第 n 项的值 
    int a[N][N]={{0,1},{1,1}};
    memset(f,0,sizeof(f)),n++;
    for(int i=0;i<N;i++) f[i][i]=1;
    for(;n;n>>=1,mul(a,a))
        if(n&1) mul(f,a);
    return f[0][0];
} 
signed main(){
    scanf("%lld%lld%lld%lld",&mod,&l,&r,&k);
    for(int i=1;i<=sqrt(r);i++){
        if(calc(i)>=k) res=max(res,i);
        if(calc(r/i)>=k) res=max(res,r/i);    //判断 calc(i) 和 calc(r/i) 是否 >=k，并记录下最大的 i 或 r/i 
    }
    printf("%lld\n",query(res));
    return 0;
}

3. Luogu P3424 [POI2005]SUM-Fibonacci Sums

题目大意：斐波那契数列：\(F_0=1,F_1=1\)，对于 \(n\geq 2\)，有 \(F_n=F_{n-1}+F_{n-2}\)。

我们可以用若干个斐波那契数列中的数的和的形式表示一个数。为了保证表示的唯一性，我们用 \(b_1,b_2,\cdots,b_n\) 表示数 \(b_1\cdot F_1+b_2\cdot F_2+\cdots +b_n\cdot F_n\)，\(b_i\in \{0,1\}\)，注意此题中没有用 \(F_0\)。并且有如下规定：

  • 若 \(n>1\)，则 \(b_n=1\)，即表示的数没有多余的零。

  • 若 \(b_i=1\)，则 \(b_{i+1}=0\)（\(1\leq i<n\)），即表示中不存在两个（或以上）连续的 \(1\)。

已知 \(x,y\) 的斐波那契表示，求 \(x+y\) 的斐波那契表示。

Solution：

首先把两个数列对应位置上的数分别加起来，再进行调整。令 \(c_i=a_i+b_i\)。

若存在 \(c_i>1\)：

  • 若 \(i=1\)，由于 \(F_2=F_0+F_1=2F_1\)，则令 \(c_1←c_1-2\)，\(c_2←c_2+1\)。

  • 否则：由于 \(2F_n=F_{n-1}+F_n+F_{n-2}=F_{n+1}+F_{n-2}\)，则可以令 \(c_i←c_i-2\)，\(c_{i+1}←c_{i+1}+1\)，\(c_{i-2}←c_{i-2}+1\)。

若出现 \(c_i=1\)，\(c_{i+1}=1\)，由于 \(F_n=F_{n-1}+F_{n-2}\)，则可以令 \(c_i←c_i-1\)，\(c_{i+1}←c_{i+1}-1\)，\(c_{i+2}←c_{i+2}+1\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,up,a[N],b[N],c[N];
void solve(int x){    //处理 c[x]>1 的情况 
    if(c[x]<=1) return ;
    c[x]-=2;
    if(x==1) c[2]++;
    else if(x==2) c[1]++,c[3]++;
    else c[x+1]++,c[x-2]++;
}
void work(int x){    //处理连续两个数都为 1 的情况 
    while(c[x]>0&&c[x+1]>0) c[x]--,c[x+1]--,c[x+2]++,x+=2;
} 
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    scanf("%lld",&m),up=max(n,m);
    for(int i=1;i<=m;i++)
        scanf("%lld",&b[i]);
    for(int i=1;i<=up;i++)    //先直接加起来 
        c[i]=a[i]+b[i];
    for(int i=up;i>=1;i--)
        solve(i),work(i),solve(i+1),work(i+1),solve(i+2),work(i+2);     //最多影响到后面两位，i+1 和 i+2 也要判 
    if(c[up+1]) up++; if(c[up+2]) up+=2;    //进位。最多影响到后面两位
    printf("%lld ",up);
    for(int i=1;i<=up;i++)
        printf("%lld%c",c[i],i==up?'\n':' ');
    return 0;
}

五、习题

  • Luogu P3539 [POI2012]ROZ-Fibonacci Representation
  • SPOJ MAIN74 - Euclids algorithm revisited
  • CF633D Fibonacci-ish
  • UVA10236 The Fibonacci Primes

推荐阅读