斐波那契数列
\(F(0)=F(1)=1\) 或 \(F(1)=F(2)=1\),\(F(i)=F(i-1)+F(i-2)\).
广义斐波那契数列在转移时有系数且首两项给定。
求法
注意到斐波那契数列的转移为一个矩阵乘 \[
\begin{bmatrix}F(i)&F(i-1)\end{bmatrix}
\begin{bmatrix}
1&1\\
1&0
\end{bmatrix}
\] 当然广义斐波那契数列的转移就是把转移矩阵的系数换了一下。
所以我们可以通过矩阵快速幂快速求得所求项数。
给出广义斐波那契数列的矩阵乘代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #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]\)。
更形式化地讲,从大到小枚举斐波那契数,每当$ F[i]\(不小于当前数就将此位置为1并减去该\)
F[i]$,根据定理最后一定会被减完,即被一个01串表示。
因为斐波那契数的增长速度很快,所以这个串并不会很长。
我们来看个毒瘤题:
P6791 [SNOI2020]
取石子
对于这个LCA的毒瘤题本身我并不会没什么好说的,没有发现打表之外的解法
通过打表我们可以发现,设\(a_i\)表示还剩i颗石子时甲必胜此次至少要取的石子个数,那么
\(a_i\) 为 \(i\) 在斐波那契进制下的 lowbit。
所以这个题本身和斐波那契数就只有这么点关系
对于题本身不予讨论。我也不会证
斐波那契公约数
P1306
我们需要证明\(F[\gcd(i,j)]=\gcd(F[i],F[j])\)。
其中\(F[0]=F[1]=1\)。
- 引理:\(\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])=\dots=\gcd(F[2],F[1])=1
\] 即\(F[i]\)与\(F[i-1]\)互质。
- 引理:\(F[m+n]=F[m-1]F[n]+F[m]F[n+1]\)
设\(F[n]=a,F[n+1]=b\),向下递推发现由\(a\)和\(b\)表达的\(F[i]\)中其系数是斐波那契数。自己推推就知道了。
- \(F[\gcd(i,j)]=\gcd(F[i],F[j])\)
证明:
不妨设\(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])
\] 即 \[
\gcd(F[i],F[j])=\gcd(F[i],F[j\mod i])
\] 递归求解,发现我们就是在对F的下标求gcd,也就是 \[
\gcd(F[i],F[j])=F[\gcd(i,j)] \\ \square
\]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| #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\)
还是设\(F[i]=a,F[i+1]=b\),然后推来推去,具体看@浅色调 的过程
对于P3986,这个结论可以用来快速解决
\(aF[i]+bF[i+1]=k\) 而不用exgcd。
即有通解 \(x=k*(-1)^iF[i-1],y=k*(-1)^{i+1}F[i-2]\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #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; }else if(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\),设 \(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]
\] 设\(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]
\] 和斐波那契数列的转移相同。
板子题
总结
斐波那契数列性质很多。之后遇到新的我应该会补。
如果您凑巧看到了这里并知道一些相关题目请不吝赐教~