斐波那契数列相关

发布时间：2025-01-05 21:26

斐波那契数列

F(0)=F(1)=1" role="presentation">F(0)=F(1)=1或F(1)=F(2)=1" role="presentation">F(1)=F(2)=1，F(i)=F(i−1)+F(i−2)" role="presentation">F(i)=F(i−1)+F(i−2).

广义斐波那契数列在转移时有系数且首两项给定。

求法

注意到斐波那契数列的转移为一个矩阵乘

F(i)F(i−1)        1110" role="presentation">F(i)F(i−1) 1110

当然广义斐波那契数列的转移就是把转移矩阵的系数换了一下。

所以我们可以通过矩阵快速幂快速求得所求项数。

给出广义斐波那契数列的矩阵乘代码：

#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define int long long using namespace std; inline int read(){int w=0,x=0;char c=getchar();while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x; } namespace star {int mod;struct mat{int a[2][2];inline void set(){memset(a,0,sizeof a);}inline void zero(){set();a[0][0]=a[1][1]=1;}inline int* operator [] (const int x){return a[x];}inline const int* operator [] (const int x) const {return a[x];}inline mat operator * (const mat &b)const{mat ans;ans.set();for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;return ans;}}now,pow;inline mat fpow(mat a,int b){mat ans;ans.zero();for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;return ans;}inline void work(){int p=read(),q=read(),a1=read(),a2=read(),n=read();mod=read();now[0][1]=a1,now[0][0]=a2,pow[0][0]=p,pow[1][0]=q,pow[0][1]=1;printf("%lld",(now*fpow(pow,n-1))[0][1]);} } signed main(){star::work();return 0; }

性质

斐波那契数具有很多神奇的性质，虽然有些不太常用

齐肯多夫定理：任何正整数可以表示为若干个不连续的斐波那契数之和。

于是我们可以引出来一个叫做斐波那契进制的东西。

简单来说，因为任何数都可以被若干个斐波那契数的和表示，我们就可以把这个数用01串表示。其中第i位表示是否含有F[i]" role="presentation">F[i]。

更形式化地讲，从大到小枚举斐波那契数，每当$ F[i]不小于当前数就将此位置为1并减去该" role="presentation">不小于当前数就将此位置为1并减去该 F[i]$，根据定理最后一定会被减完，即被一个01串表示。

因为斐波那契数的增长速度很快，所以这个串并不会很长。

我们来看个毒瘤题：

P6791

对于这个LCA的毒瘤题本身我并不会没什么好说的，没有发现打表之外的解法

通过打表我们可以发现，设ai" role="presentation">ai表示还剩i颗石子时甲必胜此次至少要取的石子个数，那么ai" role="presentation">ai为i" role="presentation">i在斐波那契进制下的lowbit。

所以这个题本身和斐波那契数就只有这么点关系

对于题本身不予讨论。我也不会证

斐波那契公约数

P1306

我们需要证明F[gcd(i,j)]=gcd(F[i],F[j])" role="presentation">F[gcd(i,j)]=gcd(F[i],F[j])。

其中F[0]=F[1]=1" role="presentation">F[0]=F[1]=1。

引理：gcd(F[i],F[i−1])=1" role="presentation">gcd(F[i],F[i−1])=1

证明：

gcd(F[i],F[i−1])=gcd(F[i]−F[i−1],F[i−1])=gcd(F[i−1],F[i−2])=⋯=gcd(F[2],F[1])=1" role="presentation">gcd(F[i],F[i−1])=gcd(F[i]−F[i−1],F[i−1])=gcd(F[i−1],F[i−2])=⋯=gcd(F[2],F[1])=1

即F[i]" role="presentation">F[i]与F[i−1]" role="presentation">F[i−1]互质。

引理：F[m+n]=F[m−1]F[n]+F[m]F[n+1]" role="presentation">F[m+n]=F[m−1]F[n]+F[m]F[n+1]

设F[n]=a,F[n+1]=b" role="presentation">F[n]=a,F[n+1]=b,向下递推发现由a" role="presentation">a和b" role="presentation">b表达的F[i]" role="presentation">F[i]中其系数是斐波那契数。自己推推就知道了。

F[gcd(i,j)]=gcd(F[i],F[j])" role="presentation">F[gcd(i,j)]=gcd(F[i],F[j])

证明：

不妨设i<j" role="presentation">i<j，则有

gcd(F[i],F[j])=gcd(F[i],F[j−i−1]F[i]+F[j−i]F[i+1])=gcd(F[i],F[j−i]F[i+1])=gcd(F[i],F[j−i])" role="presentation">gcd(F[i],F[j])=gcd(F[i],F[j−i−1]F[i]+F[j−i]F[i+1])=gcd(F[i],F[j−i]F[i+1])=gcd(F[i],F[j−i])

即

gcd(F[i],F[j])=gcd(F[i],F[jmodi])" role="presentation">gcd(F[i],F[j])=gcd(F[i],F[jmodi])

递归求解，发现我们就是在对F的下标求gcd，也就是

gcd(F[i],F[j])=F[gcd(i,j)]◻" role="presentation">gcd(F[i],F[j])=F[gcd(i,j)]◻

#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define int long long using namespace std; inline int read(){int w=0,x=0;char c=getchar();while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x; } namespace star {const int mod=1e8;struct mat{int a[2][2];mat(){memset(a,0,sizeof a);}inline void zero(){a[0][0]=a[1][1]=1;}inline int* operator [] (const int x){return a[x];}inline const int* operator [] (const int x) const {return a[x];}inline friend mat operator * (const mat &a,const mat &b){mat ans;for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;return ans;}}now,pow;int gcd(int a,int b){return b?gcd(b,a%b):a;}inline mat fpow(mat a,int b){mat ans;ans.zero();for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;return ans;}inline void work(){now[0][0]=now[0][1]=pow[0][0]=pow[0][1]=pow[1][0]=1;printf("%lld",(now*fpow(pow,gcd(read(),read())-1))[0][1]);} } signed main(){star::work();return 0; } F[i−1]∗F[i+2]−F[i]∗F[i+1]=(−1)i" role="presentation">F[i−1]∗F[i+2]−F[i]∗F[i+1]=(−1)i

还是设F[i]=a,F[i+1]=b" role="presentation">F[i]=a,F[i+1]=b，然后推来推去，具体看@浅色调的过程

对于P3986，这个结论可以用来快速解决aF[i]+bF[i+1]=k" role="presentation">aF[i]+bF[i+1]=k而不用exgcd。

即有通解x=k∗(−1)iF[i−1],y=k∗(−1)i+1F[i−2]" role="presentation">x=k∗(−1)iF[i−1],y=k∗(−1)i+1F[i−2]

贴下P3986的代码：

#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<cmath> #define int long long using namespace std; inline int read(){int w=0,x=0;char c=getchar();while(!isdigit(c))w|=c=='-',c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x; } namespace star {const int maxn=100,mod=1e9+7;int N,f[maxn],ans;inline void work(){int k=read();f[1]=f[2]=1;ans=k-1;for(N=3;(f[N]=f[N-1]+f[N-2])<k;N++);N--;for(int x,y,j=2;j<=N;j++){int q=((j-1)&1)?-1:1;x=k*q*f[j+3],y=-k*q*f[j+2];if(x<0){y-=((-x)/f[j+1]+1)*f[j];if(y>0)ans=(ans+(int)ceil(1.0*y/f[j]))%mod;}elseif(y<0){x-=((-y)/f[j]+1)*f[j+1];if(x>0)ans=(ans+(int)ceil(1.0*x/f[j+1]))%mod;}}printf("%lld",ans);} } signed main(){star::work();return 0; }

PS:浅色调的题解对N多算了一次，减掉即可。或者在第二遍for循环内直接判掉break也行。

UPD10.15 给定一个长为n的序列，可在其中填1，求使1任意两个都不相邻的方案数。

昨天看了一道叫做01矩阵的题目想到该问题，经询问luogu聚铑们得到答案。

首先，

这玩意和斐波那契数有什么关系？

考虑DP，对于位置i" role="presentation">i,设f[i][0],f[i][1]" role="presentation">f[i][0],f[i][1]为前i个数填完、i填0或1的方案数，则有转移

f[i][0]=f[i−1][0]+f[i−1][1]f[i][1]=f[i−1][0]" role="presentation">f[i][0]=f[i−1][0]+f[i−1][1]f[i][1]=f[i−1][0]

设g[i]" role="presentation">g[i]为到i的方案总数，则有

g[i]=f[i][0]+f[i][1]g[i]=f[i−1][0]+f[i−1][1]+f[i−1][0]g[i]=g[i−1]+g[i−2]" role="presentation">g[i]=f[i][0]+f[i][1]g[i]=f[i−1][0]+f[i−1][1]+f[i−1][0]g[i]=g[i−1]+g[i−2]

和斐波那契数列的转移相同。

板子题