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杨惠淋是也师兄的共同探讨。
还有感谢百度知道囊中无忌的回答。
=======================签 名 档=======================
原文地址(我的博客):
http://www.clanfei.com/2012/04/373.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
杭电hdu acm资料所用杭电的acm题
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
写一个数据结构算法,杭电上一道题目,有关数据结构的题目。
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases. In each test case, there are two integers k,m(1≤k≤1018,1≤m≤100). Output For each test case, print ...
此程序为hdu的acm2010题,就是解决水仙花数问题
acm经典题、结题报告,对初学者非常用用,我就从中学到了很多东西
ACM比赛解题报告,包括hdu1880、zoj1010、zoj1015,为原创的报告,算法不一定最优的
杭电acm解题报告 详细解析2000-2099 适合acm初学者
杭电acm 一些java语言实现的水题目
杭电的一些acm题目,都是我自己一个一个自己提交的
ACM_算法模板集史上最完整收藏版223页全免费版.pd
ACM_HDU 我的 acm 问题的一部分在 hdoj 中解决了。
HDU_ACM_1002_大数相加C源代码,利用字符串处理
noi试题和解析,对于参加acm非常有帮助
浙江大学ACM题解JU_ACM_All_Anwer,里面一本非常好的chm电子书,浙大的所有ACM题及题解都在了,对学习ACM的朋友非常的好~还等什么呢?
ACM_基础篇
Pascal acm_timus_ural_1148.pas
Pascal acm_timus_ural_1099.pas
ACM__ICPC__重要补充知识.doc
常用的算法代码(排序,字符串操作,数学问题,数论,计算几何等等)