关于HDOJ 1005题的理解(C/C++)

由于博主是初来乍到的，最近又在想办法刷一下算法题，所以决定写一下自己的博客记录下这个假期的A题过程（写bug过程），题目或许有些简单，希望各位大佬不要介意吐槽。此外，特别感谢mengxiang000000以及CouchDB两位老兄的启发，帮助了原本对于该题不是TLE就是MLE的我，于是在理解的基础上算是把mengxiang000000老哥的代码用C++复述了一遍。若本篇博客涉权了，请联系左边头像下的myself（QQ就是github名的数字）。

题目描述

Problem Description
A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

Output
For each test case, print the value of f(n) on a single line.

Sample Input
1 1 3
1 2 10
0 0 0

Sample Output
2
5

Author
CHEN, Shunbao

Source
ZJCPC2004

原题链接

More info:Question

硬来？

博主拿到题后首先一看，呵，1000打头的，估计不用考虑超时超限什么的吧，直接硬上……然而，事实证明博主太年轻太天真……

hhh

Memory Limit Exceeded

#include <iostream>

using namespace std;

int fun(int n, int a, int b) {
   if (n == 1 || n==2) return 1;
   return (a * fun(n - 1, a, b) + b * fun(n - 2, a, b)) % 7;
}
int res;
int main() {
   int A, B, n;
   cin >> A >> B >> n;
   while (A && B && n) {
       res = fun(n, A, B);
       cout << res << endl;
       cin>> A >> B >> n;
   }
   return 0;
}

Memory Limit Exceeded

#include <iostream>

using namespace std;
int f1=1, f2=1, res;

int fun(int n, int a, int b) {
   if (n == 1 || n == 2) return 1;
   for (int i = 3; i <= n; i++) {
       res = (a * f2 + b * f1) % 7;
       f1 = f2;
       f2 = res;
   }
   return res;
}

int main() {
   int A, B, n;
   cin >> A >> B >> n;
   while (A && B && n) {
       fun(n, A, B);
       cout << res << endl;
       cin>> A >> B >> n;
   }
   return 0;
}

Accepted代码

//杭电oj 1005 
//f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
//Given A, B, and n, you are to calculate the value of f(n).
#include<iostream>
using namespace std;
int ans[52];//f(n-1)、f(n-2)也是%7过得数，所以f(n)的取值情况只可能是7*7=49种，用>49的数组来寻重
int main() {
int a, b, n;
while (cin >> a >> b >> n) {
	if (a == 0 && b == 0 && n == 0) break;//如果输入3个0，则退出循环，return 0

	int i;//用i找到循环的长度（周期应该为 i-2）
	ans[1] = ans[2] = 1;
	for (i = 3; i <= 49; i++) {
		ans[i] = (a * ans[i - 1] + b * ans[i - 2]) % 7;
		if (ans[i] == 1 && ans[i - 1] == 1)
			break;
	}
	ans[0] = ans[i - 2];//ans[0]之前没初始化过，而且可能出现恰好整除周期的情况
	cout << ans[n % (i - 2)] << endl;
}

return 0;
}

这里提醒一定注意ans[0]的初始化，由于代码末尾输出的时候%周期时可能出现整除的情况，然而代码中的数组并没有初始化ans[0],可能会就此点出现wrong answer的结果（大意真的会失荆州哦）
另外，有小伙伴可能会问为啥for循环到49就截止了（大佬请忽略这里），因为f(n-1)、f(n-2)也是%7过后得到的数，换言之f(n-1)取值范围在0~6中的整数，f(n-2)亦然，所以f(n)的取值情况只可能是7*7=49种，也因此，f(n)必然呈现周期性，并且周期出现在这总的49种可能之内，于是在49的长度内给它寻找周期T=i-2.（详情可以参见博客）
再次感谢两篇博客源：
mengxiang000000
CouchDB