@[Harry_Haiyun](/user/977778) 哥你能不能看看数据范围再来问
by Aisaka_Taiga @ 2023-05-28 18:11:50
@[Aisaka_Taiga](/user/526519) 一样啊。
```
#include <iostream>
using namespace std;
long long fibonacci(int n)
{
if (n < 2) return 1;
else return fibonacci(n - 1) + fibonacci(n - 2);
}
int main()
{
int n;
cin >> n;
cout << fibonacci(n - 1) << endl;
return 0;
}
//测试点与上一段代码一样
by __Harry_Haiyun__ @ 2023-05-28 18:16:06
@[Harry_Haiyun](/user/977778) 老哥 $2^{63}$ 你还递归你没事吧这得用矩阵加速
by Aisaka_Taiga @ 2023-05-28 18:17:44
@[Aisaka_Taiga](/user/526519) 哦索瑞我根本没学过矩阵加速，你教教我呗。
by __Harry_Haiyun__ @ 2023-05-28 18:19:44
数据规模是2的63次方，你这样做会超时，必须用矩阵加速才能AC
by Ilovemywinnie @ 2023-05-28 18:20:08
@[Harry_Haiyun](/user/977778) 想一想为什么这道题是绿题
by HeCao2008 @ 2023-05-28 18:20:41
@[Harry_Haiyun](/user/977778) 这个题右边有题解，你自己去看题解
by 北文 @ 2023-05-28 18:21:14
```c
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e9+7;
struct node{
ll v[5][5];
int row,col;
};
node I;//单位矩阵
node matrixMul(node A,node B){
node C={0};
C.row=A.row;C.col=B.col;
for(int i=1;i<=C.row;i++){
for(int j=1;j<=C.col;j++){
for(int k=1;k<=A.col;k++){
C.v[i][j]+=A.v[i][k]*B.v[k][j];
C.v[i][j]%=M;
}
}
}
return C;
}
node matrixPow(node A,ll n){
if(n==0) return I;
node t=matrixPow(A,n/2);
if(n&1) return matrixMul(matrixMul(t,t),A);
return matrixMul(t,t);
}
int main(){
ll n;
//处理单位矩阵
I={
{
{0,0,0},
{0,1,0},
{0,0,1}
},2,2
};
//处理原始矩阵
node a={
{
{0,0,0},
{0,1,1}
},1,2
};
//处理加速矩阵
node b{
{
{0,0,0},
{0,0,1},
{0,1,1}
},2,2
};
cin>>n;
node t=matrixPow(b,n-1);
node ans=matrixMul(a,t);
cout<<ans.v[1][1]<<endl;
return 0;
}
```
by Ilovemywinnie @ 2023-05-28 18:21:18
不玩原神导致的。
by bykem @ 2023-05-28 18:38:21
玩原神导致的。
by felixesintot @ 2023-06-18 10:12:16