[ACM_HDU_1005]Number Sequence

杰拉斯 | 时间：2012-04-01, Sun | 25,314 views
编程算法　

Number Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 53991 Accepted Submission(s): 12146

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

这是一道递推题目，但与斐波那契数列等递推题目不同的是，递推关系取决于输入的A、B，因此不能像斐波那契数列那般用空间换时间，先将数组储存起来，通过输入的数字直接查询。

#include<stdio.h>
int main(){
	int A, B, n, i;
	while(scanf("%d%d%d", &A, &B, &n) != EOF){
		if(A == 0 && B == 0 && n == 0)
			break;
		int f[3] = {1, 1, 0};
		for(i = 2; i < n; ++i){
			f[i % 3] = (A * f[(i + 2) % 3] + B * f[(i + 1) % 3]) % 7;
			printf("%d\n", f[i % 3]);
		}
		printf("%d\n", f[(i + 2) % 3]);
	}
	return 0;
}

由于限制条件(1 <= A, B <= 1000, 1 <= n <= 100,000,000)，很明显这段代码必然是Time Limit Exceeded。

我们先来看递推公式：

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

想要通过这么复杂的递推公式来找出通项，先不说是否能找出来，至少我是找不出来的。

那么对这条公式进行分析，每位数字都是通过mod 7得到，很显然，每位数字都只可能是0-6，共7种情况，因此连续两位数字的所有组合情况总数为7 * 7 = 49种，第50位数字后必然出现与之前某两位连续数字相同的情况，而每位数字都只与前两位数字有关，那么周期就出现了，且最大周期数为49。

写出代码如下：

#include<stdio.h>
int main(){
	int A, B, n, z = 1;
	int f[50] = {1, 1, 1};
	while(scanf("%d%d%d", &A, &B, &n) != EOF){
		if(A == 0 && B == 0 && n == 0)
			break;
		for(int i = 3; i < 50; ++i){
			f[i] = (A * f[i - 1] + B * f[i - 2]) % 7;
			if(f[i - 1] == 1 && f[i] == 1){
				z = i - 2;
				break;
			}
		}
		printf("%d\n", f[n % z]);
	}
	return 0;
}

示例输入跟示例输出正确，可是提交后却出现了Wrong Answer，百思不得其解，纠结了许多天，后来终于发现了问题，因为周期中不一定是从1 1开始的，因为最开始的两项1 1是题目给出的，并不符合递推公式，即不符合上面所推出的49最大周期结论。如：

输入：7 7 10

f[n]：1 1 0 0 0 0 0 ...

而直接拿1 1来判断，自然就出错了。

几经优化，最终代码如下：

#include<stdio.h>

int main(){
	int A, B, n, z = 1;
	int f[54] = {0, 1, 1};
	//取54是因为第0位不使用，第1,2位固定为1，加49最大周期及最后判断周期所用2位，最大共需用54位。
	while(scanf("%d%d%d", &A, &B, &n) != EOF){
		if(A == 0 && B == 0 && n == 0)
			break;
		for(int i = 3; i < 54; ++i){
			f[i] = (A * f[i - 1] + B * f[i - 2]) % 7;
			//printf("%d ", f[i]);
			if(i > 5){
				if(f[i - 1] == f[3] && f[i] == f[4]){
					z = i - 4;
					break;
				}
			}
		}
		//printf("\n%d\n", z);
		if(n > 2)
			printf("%d\n", f[(n - 3) % z + 3]);
		else
			printf("1\n");
	}
	return 0;
}

结果Accepted，该题解决。。感谢超钧哥的指导及@Alex杨惠淋是也师兄的共同探讨。

还有感谢百度知道囊中无忌的回答。

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客