Blog·Tanky WooABOUTRSS

HDOJ 1005 Number Sequence

25 Jul 2010
这篇博客是从旧博客 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;
}