题目大意

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房M开始爬到蜂房N,M<N,有多少种爬行路线?M,N<=1000

题解

看到M,N<=1000,我们不能寻求通项解。我们从动规的角度看,令f(i)为从1到达编号为i的蜂房爬行路线总数,则f(i)=f(i-1)+f(i-2)。这就是斐波那契数的定义呀!求f(n-m)即可。注意斐波那契数很大,要用到高精度。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int MAX_LEN = 1001, BASE = 10000, CARRY = 4; struct BigInt
{
private:
int A[MAX_LEN];
int Len; public:
BigInt()
{
memset(A, 0, sizeof(A));
Len = 0;
} BigInt& operator += (const BigInt& a)
{
for (int i = 0; i <= max(Len, a.Len); i++)
{
A[i] += a.A[i];
A[i + 1] += A[i] / BASE;
A[i] %= BASE;
}
if (A[Len + 1])
Len++;
return *this;
} BigInt& operator = (const BigInt& a)
{
memcpy(A, a.A, sizeof(A));
Len = a.Len;
return *this;
} BigInt& operator = (int x)
{
memset(A, 0, sizeof(A));
Len = 0;
while (x)
{
A[Len++] = x%BASE;
x /= BASE;
}
while (Len > 0 && A[Len] == 0)
Len--;
return *this;
} BigInt operator +(const BigInt& a)
{
BigInt ans = *this;
return ans += a;
} void Print()
{
printf("%d", A[Len]);
for (int i = Len - 1; i >= 0; i--)
printf("%0*d", CARRY, A[i]);
}
}; BigInt& GetF(int n)
{
static BigInt F[3];
F[0] = 1;
F[1] = 1;
for (int i = 2; i <= n; i++)
F[i % 3] = F[(i - 1) % 3] + F[(i - 2) % 3];
return F[n % 3];
} int main()
{
int n, m;
scanf("%d%d", &m, &n);
GetF(n - m).Print();
return 0;
}

  

最新文章

  1. 使用SSIS进行数据清洗
  2. Unix网络编程--卷二:FAQ
  3. crossplatform---Nodejs in Visual Studio Code 06.新建Module
  4. Swing应用开发实战系列之一:自定义JdbcTemplate
  5. windows系统调用 进程快照
  6. C# OpenFileDialog和PictrueBox
  7. 转:12种JavaScript MVC框架之比较
  8. OpenNMS架构介绍
  9. js实现图片自动切换效果。
  10. 使用Docker官方的Django包【转】
  11. STM32的FSMC总线复用调试笔记
  12. web开发性能优化---UI接口章
  13. 《12个有趣的C语言问答》评析2
  14. 自动化测试框架 hierarchyViewer、Uiautomator、Appium的区别比较!
  15. 浅析Java数据类型
  16. day14
  17. H5-手机震动
  18. jQuery Ajax -附示例
  19. Spring Boot(八):RabbitMQ详解
  20. Git 基础 - 打标签

热门文章

  1. js数据管理的思考
  2. bootstrap的栅格系统和响应式工具
  3. 精确获取对象的类型:Object.prototype.toString()
  4. jquery中的left和top
  5. CSS的常用属性(一)
  6. How to add jdk8 in Eclipse Indigo
  7. HDU_1850_nim游戏
  8. HDU_5833_高斯消元
  9. Super Poker II UVA - 12298 FFT_生成函数
  10. 使用for或while循环来处理处理不确定页数的网页数据爬取