这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1005
曾经失败过,今天怀着论坛挂了的沉重心情再做了一次,先准备用上hash表的。
后来一想,数据很小的,必然会再前50次里碰到开始循环的局面。
为何?
思路:
因为循环的条件就是有2个数m和n
f[m-1] = f[n-1], f[m] = f[n]
这样就会开始循环了。
即f[n-1], f[n]与之前的[m-1],f[m]分别对应
而 0 <= f[n-1],f[n] < 7
所以f[n-1]f[n]连着的情况有7*7的情况。
只需每次求出一个f[n],然后比较f[n-1]f[n]与前面数的情况即可。
代码:
// Author: Tanky Woo
// HDOJ 1005
// Accepted 1005 0MS 276K 815B G++ Tanky Woo
#include
int f[60];
int a, b, c; // 分别代表f[i-2], f[i-1], f[i];
int A, B, n;
int main()
{
while(scanf("%d %d %d", &A;, &B;, &n;) && (A||B||n))
{
memset(f, 0, sizeof(f));
f[1] = 1;
f[2] = 1;
// f[n] = A*f[n-1]+B*f[n-2] = A*b+B*a;
a = 1; // f[n-2]
b = 1; // f[n-1]
c = (A+B)%7;
int cnt = 0, loop = 0;
for(int i = 3; i < 60; ++i)
{
f[i] = c;
a = b;
b = c;
c = (A*b+B*a)%7;
for(int j = 2; j < i; ++j)
if(f[j-1] == f[i-1] && f[j] == f[i])
{
cnt = j; //从cnt开始循环
loop = i-j; // 循环数
break;
}
}
if(n < cnt)
printf("%d\n", f[n]);
else
printf("%d\n", f[cnt+(n-cnt)%loop]);
}
return 0;
}