#1005 Number Sequence

http://acm.hdu.edu.cn/showproblem.php?pid=1005

一看以为只是个普通的递归调用，写完如下

 1 #include<stdio.h>
 2 
 3 int A, B;
 4 int f(int n)
 5 {
 6     if (n == 1 || n == 2)
 7     {
 8         return 1;
 9     }
10     return (A*f(n - 1) + B*f(n - 2)) % 7;
11 }
12 int main()
13 {
14     int n;
15     while (scanf("%d %d %d", &A, &B, &n) && A!=0 && B!=0 && n!=0)
16     {
17         printf("%d
", f(n));
18     }
19     return 0;
20 }

结果一提交报错Memory Limit Exceeded超出内存限制，慌了，没遇到过。

题目的n输入范围是0到一亿，这是一个相当大的数字，递归那么多次必然要超出内存限制了。

百度了一下发现在17行处改为

printf("%d
", f(n%49));

就能AC了，并不能理解，再看看其他人的答案，连递归都不见了，我是不是错过了什么。。。我再找找原因。

看了一下，由于f()的返回值只会是0-6的数字，只有7种可能，而AB每次运算都是不变的，所以每一组ABN的数据中

A*f(n-1)+B*F(n-2)

最多只会有49种结果，输入的时候把n余一下49，可减少计算量。

我反正是没懂，这不是递归嘛？为什么我看的其他人都在找规律都在打什么表。。。看不懂啊