Luogu P2437 Bee Route

Title description

A bee is crawling on the numbered hive as shown in the figure below. It is known that it can only crawl from the hive with a small number to the adjacent hive with a large number. Now I ask you: the bee starts from hive m to hive n,m

Input format

Enter the value of m,n

Output format

How many routes are there for crawling

Sample input and output

Enter #1Copy

1 14

Output #1Copy

377

Instructions/Tips

For 100% data, 1≤M,N≤1000

Problem solving ideas:

From the title, it is not difficult to find that the solution of the problem is similar to the Fibonacci sequence, that is, f[i]=f[i-1]+f[i-2].Here we have completed the first step.In the second step, since the data in this question is large and exceeds the range, we also need to perform high-precision addition processing.

The code is as follows:

#include using namespace std;int m, n,len=1;int c[1005][1005];void compute(int index) {int i=1,x=0;while (i <= len) {c[index][i] = c[index-1][i] + c[index-2][i] + x;x = c[index][i] / 10;c[index][i] %= 10;i++;}if (x != 0) {c[index][len + 1] = x;len++;}}int main() {cin >> m >> n;c[m + 1][1] = 1;c[m + 2][1] = 2;for (int i = m + 3; i <= n; i++) {compute(i);}for (int i = len; i >= 1; i--) {cout << c[n][i];}return 0;}