题目既然都说了记忆化记忆化，咱就来个记忆化！ 我就不信啦，还能WA 备注：数组内容为(LONG LONG类型)：1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,1548008755920 1~100位(DOUBLE类型)：1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1.34627E+06,2.17831E+06,3.52458E+06,5.70289E+06,9.22746E+06,1.49304E+07,2.41578E+07,3.90882E+07,6.3246E+07,1.02334E+08,1.6558E+08,2.67914E+08,4.33494E+08,7.01409E+08,1.1349E+09,1.83631E+09,2.97122E+09,4.80753E+09,7.77874E+09,1.25863E+10,2.0365E+10,3.29513E+10,5.33163E+10,8.62676E+10,1.39584E+11,2.25851E+11,3.65435E+11,5.91287E+11,9.56722E+11,1.54801E+12,2.50473E+12,4.05274E+12,6.55747E+12,1.06102E+13,1.71677E+13,2.77779E+13,4.49456E+13,7.27235E+13,1.17669E+14,1.90392E+14,3.08062E+14,4.98454E+14,8.06516E+14,1.30497E+15,2.11149E+15,3.41645E+15,5.52794E+15,8.94439E+15,1.44723E+16,2.34167E+16,3.78891E+16,6.13058E+16,9.91949E+16,1.60501E+17,2.59695E+17,4.20196E+17,6.79892E+17,1.10009E+18,1.77998E+18,2.88007E+18,4.66005E+18,7.54011E+18,1.22002E+19,1.97403E+19,3.19404E+19,5.16807E+19,8.36211E+19,1.35302E+20,2.18923E+20,3.54225E+20,3.54225E+20

采用递归，dfs(x)dfs(x)dfs(x) 的返回值是第 xxx 项斐波那契数列的值，则输出 dfs(n)dfs(n)dfs(n),递归的终止条件可以是当 x=1x=1x=1 或 x=2x=2x=2 时，返回 111。单纯的递归会超时，可以采用记忆化，用数组存储答案。

显然这题可以用矩阵快速幂完成，起始矩阵是斐波那契数列前两项 [11] \begin{bmatrix} 1\\ 1 \end{bmatrix} [11 ]，转移矩阵是 [1110]\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}[11 10 ]，即矩阵递推式 [f(i)=1×f(i−1)+1×f(i−2)f(i)=1×f(i−1)+0×f(i−2)]\begin{bmatrix} f(i)=1\times f(i-1)+1\times f(i-2)\\ f(i)=1\times f(i-1)+0\times f(i-2) \end{bmatrix}[f(i)=1×f(i−1)+1×f(i−2)f(i)=1×f(i−1)+0×f(i−2) ] 中各项的系数。时间复杂度是 O(log⁡n)O(\log n)O(logn) 的，跑得飞快，加上模数后 nnn 在 long long\text{long long}long long 范围都能轻松跑过。

#include<iostream> using namespace std; long long a[65]={0,1,1}; long long man(long long n){ if(a[n]) return a[n]; return a[n]=man(n-1)+man(n-2); } int main(){ long long n; cin>>n; cout<<man(n); return 0; }

用列表！

制造这个的方法：

#include<bits/stdc++.h> using namespace std; int main(){ int n; long long a[60]; cin>>n; a[1]=1; a[2]=1; for(int i=3;i<=n;i++){ a[i]=a[i-1]+a[i-2]; } cout<<a[n]; return 0; }

#include<bits/stdc++.h> using namespace std; int main(){ long long ac;//开大点没毛病。 cin>>ac; long long wa[ac+1]; wa[0]=1; wa[1]=1; for(int i=2;i<=ac;++i)wa[i]=wa[i-1]+wa[i-2];//公式a[i-1]+[a[i-2]; cout<<wa[ac-1]<<endl; }

#include<bits/stdc++.h> using namespace std; long long z[65]={0,1,1}; long long f(long long n){ if(z[n]) return z[n]; return z[n]=f(n-1)+f(n-2); } int main(){ long long n; cin>>n; cout<<f(n); return 0; }

#include<bits/stdc++.h> using namespace std; long long b[114514]; long long f(int n) { if(b[n]!=0) { return b[n]; } if(n<=2) { return b[n]=1; } else { return b[n]=f(n-1)+f(n-2); } } int main() { int n; cin>>n; cout<<f(n); return 0; }