【算法分析】 求蜜蜂从 xxx 到 yyy 所有可能的方案数。 aia_iai 表示跨越 iii 格的方案数。 从 111 到 222 可能的路径为：1->2，a[1] = 1; 从 111 到 333 可能的路径为: 1->2->3，1->3，a[2] = 2; 从 111 到 444 可能的路径为: 1->2->3->4，1->3->4，1->2->4，a[3] = 3; 得出爬 nnn 个格子的方案数为：aia_iai = ai−1a_{i-1}ai−1 + ai−2a_{i - 2}ai−2 。 【参考代码】 【时间复杂度】 O(n)O(n)O(n) 【预计得分】 100pts100pts100pts

必须用long long不然会超

题目大意 通过递推求出蜂房 aaa 到蜂房 bbb 有多少种方法 考纲知识点 基础数据类型、控制语句结构、递推的使用方法、变量的定义以及使用 数据范围 NNN(((000 <<< NNN ≤≤≤ 100100100))) aaa 和 bbb(((000 <<< aaa <<< bbb ≤≤≤ 505050))) 解题思路 1. 举个例子: 1.1 蜂房 111 到蜂房 222 只有 111 种方法，直接到达 1.2 蜂房 111 到 333 共有 222 种方法，分别是直接到达和经过蜂房 222 1.2 蜂房 111 到 444 共有 333 种方法，分别是经过蜂房 333 到达、经过蜂房 222 到达、经过蜂房 222 再到蜂房 333 ，最后到达蜂房 444 2. 根据 1 的推导和往后的计算，我们可以得出: 2.1 蜂房编号相差为 111 的永远只有 111 个方法到达 2.2 蜂房编号相差为 222 的永远只有 222 个方法到达 2.3 从第 333 个蜂房开始，行走路线方案为前两个蜂房行走路线方案相加 先定义一个数组 aaa ，定义 aaa 的前两项(a[1]a[1]a[1] === 111、a[2]a[2]a[2] === 222) 从 333 开始循环到 505050 (因为NNN(((000 <<< NNN ≤≤≤ 100100100))))，后面再调用 第 222 个循环，输出数组 aaa 中 xxx −-− yyy 的值 参考程序 时间复杂度 O(50+n)O(50 + n)O(50+n)

翻版兔子数列（一定要开long long）

🐝 问题本质分析 这道题的核心是斐波那契数列的变形应用。我们可以用递推的思路拆解问题： 设 f(n) 表示从蜂房1爬到蜂房n的路线数 观察蜂房结构可以发现：要到达蜂房n，最后一步只能从蜂房n-1或蜂房n-2爬过来 因此递推公式为：f(n) = f(n-1) + f(n-2) 初始条件：f(1)=1（起点就是1，只有1种方式），f(2)=1（从1到2只有1条路） 📝 针对a到b的转化 题目要求从a爬到b，相当于计算从1爬到b-a+1的路线数。比如： 从3到6，间隔为6-3=3，对应计算f(4)（因为3到4是第1步，3到5是第2步，3到6是第3步，对应f(3+1)=f(4)） 代入递推公式：f(3)=f(2)+f(1)=2，f(4)=f(3)+f(2)=3，和样例结果一致 💻 代码实现（C++版本） 🎯 关键注意事项 数据范围：当b-a达到49时，结果会超过int的范围（约2e9），所以需要用long long类型存储 预计算优化：先把所有可能的结果算好存起来，每次查询直接输出，时间复杂度O(1) 递推边界：一定要注意初始条件的正确性，这是递推类问题的核心