主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
P1962 斐波那契数列 题解
最后更新于 2025-07-31 08:41:00
作者
yeyixuan
分类
题解
题解
P1962
复制 Markdown
查看原文
删除文章
更新内容
## 1. 题目大意 给定一个斐波那契数列,求第n项 %1000000007。 ## 2.60分思路 递推,时间复杂度 $O(n)$ ,~~(肯定过不了,别抄啊)~~ 代码: ```cpp #include<bits/stdc++.h> using namespace std; long long a[93]; long long mod=1000000007; int main(){ long long n; cin>>n; a[1]=1; a[2]=1; for(long long i=3;i<=n;i++){ a[i]=a[i-1]+a[i-2]; a[i]%=mod; } cout<<a[n]; return 0; } ``` ## 3.100分思路 再说方法前,我们要懂何为矩阵。 ### 矩阵 一个 $n*m$ 大小的矩阵就是一个 $n$ 行$m$列的表格,每个格子里都是数字。 ### 加法 要求:大小一样 方法:$1$号矩阵第$i$行$j$列 $+$ $2$号矩阵第$i$行$j$列 $=$ $3$号矩阵第$i$行$j$列。 很简单,代码不展示了。 ### 乘法 要求:一号的列数和二号矩阵行数一样,结果为x1行y2列。 方法:看眼代码,有注释。 ```cpp #include<bits/stdc++.h> using namespace std; int x,xx,y,yy,a[105][105],b[105][105],c[105][105]; int main(){ cin>>y>>x>>yy>>xx; for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) cin>>a[i][j]; for(int i=1;i<=xx;i++) for(int j=1;j<=yy;j++) cin>>b[i][j]; for(int i=1;i<=x;i++){ for(int j=1;j<=yy;j++){ for(int m=1;m<=xx;m++){ c[i][j]+=a[i][m]*b[m][j];//重点在这,c[i][j]是a的i行和b的j列相乘 } cout<<c[i][j]<<" "; } cout<<endl; } return 0; } ``` 不过这也太麻烦了,建议这么写 ```cpp #include<bits/stdc++.h> using namespace std; int x,xx,y,yy; struct Mat{ int n,m,a[105][105]; Mat(){} Mat(int _n,int _m){ n=_n; m=_m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) a[i][j]=0; } } void print(){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<a[i][j]<<" "; cout<<endl; } } }; Mat operator * (const Mat &lhs,const Mat &rhs){ Mat ret(lhs.n,rhs.m); for(int i=1;i<=x;i++){ for(int j=1;j<=yy;j++){ for(int m=1;m<=xx;m++) ret.a[i][j]+=lhs.a[i][m]*rhs.a[m][j]; } } return ret; } int main(){ cin>>y>>x>>yy>>xx; Mat a(x,y); Mat b(xx,yy); for(int i=1;i<=x;i++){ for(int j=1;j<=y;j++) cin>>a.a[i][j]; } for(int i=1;i<=xx;i++){ for(int j=1;j<=yy;j++) cin>>b.a[i][j]; } (a*b).print(); return 0; } ``` ~~(愣着干啥啊,赶紧去装b啊)~~ ### 矩阵快速幂 先说一个东东,单位矩阵: 就是对角线为$1$的矩阵 快速幂要求乘法结合律,巧了,矩阵也有。很容易想通,但严格证明太难了。 代码在这: ```cpp Mat ksm(Mat x,int y){ Mat ret=I();//单位矩阵的意思 while(y--){ if(y&1) ret=ret*x; x=x*x; y>>=1; } return ret; } ``` ## 回归正题 考虑这个矩阵 $x$ ,使得 $(f1,f2)* x = (f2,f3)$ $x=0,1 ;1,1$ 所以, $(f1,f2)* x^n/x^2 = (f(n-1),fn)$ 时间复杂度: $O(logn)$ 好激动啊!! 上代码 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; struct Mat{ int n,m; ll a[3][3]; Mat(){} Mat(int _n,int _m){ n=_n; m=_m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) a[i][j]=0; } } }; Mat operator * (const Mat &lhs,const Mat &rhs){ Mat ret(lhs.n,rhs.m); for(int i=1;i<=lhs.n;i++){ for(int j=1;j<=rhs.m;j++){ for(int k=1;k<=lhs.m;k++) ret.a[i][j]=(ret.a[i][j]+lhs.a[i][k]*rhs.a[k][j])%mod; } } return ret; } Mat author(int n){ Mat ret(n,n); for(int i=1;i<=n;i++){ ret.a[i][i]=1; } return ret; } Mat ksm(Mat x,ll y){ Mat ret=author(x.n); while(y){ if(y&1) ret=ret*x; x=x*x; y=y/2; } return ret; } int main(){ long long n; cin>>n; if(n==1) cout<<1; else { Mat a(2,2); a.a[1][1]=0,a.a[1][2]=1; a.a[2][1]=1,a.a[2][2]=1; Mat f(1,2); f.a[1][1]=1,f.a[1][2]=1; Mat ret=f*ksm(a,n-2); cout<<ret.a[1][2]; } return 0; } ``` ~~(求求给孩子一个赞吧)~~
正在渲染内容...
点赞
2
收藏
1