【题目来源】https://www.luogu.com.cn/problem/P2437【题目描述】一只蜜蜂在下图所示的数字蜂房上爬动已知它只能从标号小的蜂房爬到标号大的相邻蜂房现在问你蜜蜂从蜂房 m 开始爬到蜂房 nmn有多少种爬行路线【输入格式】输入 mn 的值。【输出格式】爬行有多少种路线【输入样例】1 14【输出样例】377【说明/提示】对于100%的数据1≤M,N≤1000【算法分析】● 由题意可知蜜蜂只能从标号小的蜂房爬到标号大的相邻蜂房。因此想要到达第 i 号蜂房上一步只能在 i-1 号蜂房或是在 i-2 号蜂房均可一步直接走到 i。所以若设 f[i] 表示蜜蜂爬到第 i 号蜂房的路线数则f[i]f[i-1]f[i-2]。● 蜜蜂从蜂房 m 开始爬到蜂房 nmn经过 n-m1 个蜂房。依据前述分析相当于求斐波那契数列的第 n-m1 项。● 高精度加法https://blog.csdn.net/hnjzsyjyj/article/details/144656955易看出路线数f[i]f[i-1]f[i-2]为斐波那契数列。由于 long long 最大能表示到斐波那契数列的第 92 项其值为 7,540,113,804,746,346,429。而本题可取到第 1000 项因此需要使用高精度加法。【算法代码】#include bits/stdc.h using namespace std; const int maxn5e35; string s[maxn]; string hiAdd(string a,string b) { string c; int t0; int ia.size()-1,jb.size()-1; while(i0 || j0) { if(i0) t(a[i]-0); if(j0) t(b[j]-0); c(t%100); t/10; i--,j--; } if(t!0) c(t0); reverse(c.begin(),c.end()); return c; } int main() { int m,n; cinmn; s[1]s[2]1; for(int i3; in-m1; i) { s[i]hiAdd(s[i-1],s[i-2]); } couts[n-m1]; return 0; } /* in: 1 14 out: 377 */【参考文献】https://www.luogu.com.cn/problem/solution/P2437https://www.cnblogs.com/IronMan-PZX/p/18132981