4043 - 蜜蜂路线
一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房M开始爬到蜂房N，M<N，有多少种爬行路线？
Input
输入M，N的值，1≤m<n≤1000。
Output
爬行有多少种路线。
Examples
Input
1 14
Output
377
Solution 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; }