斐波那契数列

斐波那契数列是一个很神奇的东西，今天我们就来谈一谈它。 前言：本篇博客中会有大量的公式，每一个公式都会给出严谨的证明（证明方法都是最严谨的~~数学归纳法~~） #### 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}$ 关于矩阵乘法的其他内容本文不再阐述，推荐洛谷日报：[从零开始的矩阵乘法](https://shehuizhuyihao.blog.luogu.org/post-zhen-sheng-fa) 时间复杂度：$O(log(n))$ 模板题：P1962 [斐波那契数列](https://www.luogu.org/problemnew/show/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 [斐波那契公约数](https://www.luogu.org/problemnew/show/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.线段树 众所周知，线段树可以处理很多关于区间的问题 （如果对线段树没有了解的，推荐洛谷日报[浅谈线段树](https://pks-loving.blog.luogu.org/senior-data-structure-qian-tan-xian-duan-shu-segment-tree)或者我的博客[线段树1](https://www.cnblogs.com/Robin20050901/p/9870070.html)，[线段树2](https://www.cnblogs.com/Robin20050901/p/9876321.html)，[线段树3](https://www.cnblogs.com/Robin20050901/p/10040699.html)）  这是关于数列操作的一个表格。 注意到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$ 所以原命题成立 然后用矩阵乘法计算即可。 --- #### 参考文献 - [斐波那契数列的一些引理和相关题目](https://www.cnblogs.com/fengxunling/p/9674764.html) - [Codeforces446C - DZY Loves Fibonacci Numbers Portal](https://www.cnblogs.com/VisJiao/p/Cf446C.html) 衷心的感谢以上的文献 #### 推荐文献 - 矩阵乘法：[从零开始的矩阵乘法](https://shehuizhuyihao.blog.luogu.org/post-zhen-sheng-fa) - 线段树：[浅谈线段树](https://pks-loving.blog.luogu.org/senior-data-structure-qian-tan-xian-duan-shu-segment-tree)或者我的博客[线段树1](https://www.cnblogs.com/Robin20050901/p/9870070.html)，[线段树2](https://www.cnblogs.com/Robin20050901/p/9876321.html)，[线段树3](https://www.cnblogs.com/Robin20050901/p/10040699.html)） 完结撒花！ --- #### 后记： 在翻阅洛谷日报的时候，我发现很多的算法都已经介绍了， 唯独没有神奇的斐波那契数列，于是心血来潮，写下了这篇文章。