游客 注册 | 登录
中文 | En

4043 - 蜜蜂路线

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

题目输入

输入M，N的值，1≤m<n≤1000。

题目输出

爬行有多少种路线。

输入/输出样例

输入格式

1 14

输出格式

377

C++解答

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 505;
int a[N],b[N],c[N];

void add(int a[],int b[],int c[]){
	fill(c,c+N,0);
	c[0]=b[0];
	for (int i=1; i<=c[0]; i++){
		c[i]+=a[i]+b[i];
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	if (c[c[0]+1]) c[0]++;
}

void fibo(int n){
	if (n<=2) { c[0]=1; c[1]=n; return; }
	a[0]=a[1]=b[0]=1; b[1]=2;
	for (int i=3; i<=n; i++){
		add(a,b,c);
		memcpy(a,b,sizeof(b));
		memcpy(b,c,sizeof(c));
	}
}

void output(int a[]){
	for (int i=a[0]; i>=1; i--) cout<<a[i];
	cout<<endl;
}

int main(){
	int m,n;
	cin>>m>>n;
	fibo(n-m);
	output(c);
	return 0;
}
请先登陆