HDOJ1005 Number Sequence

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

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

===========================================
按照PPT里面的说法，就是“对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。”
由于是mod7的关系，函数f两个参数，都是0~6范围内的，所以共计7*7=49种可能性，这是其一，避免重复计算。
其二，http://www.cnblogs.com/Lyush/archive/2011/09/04/2165927.html里面所说一般，这种东西肯定是有循环的，循环节最大50，何时找到循环呢？两个参数一样的时候呗。这个问题困扰了我一晚上，今天早上实在忍不住搜博客搜到了…所以自己还是太年轻了吧
这两点搞定了，就没有任何问题了。

#include 
using namespace std;
int f(int A, int B, unsigned long n)
{
    if(n == 2 || n == 1)
        return 1;
    int mat[7][7];
    int looked[7][7];
    for(int i=0; i<7; i++)
    {
        for(int j=0; j<7; j++)
        {
            mat[i][j] = (A*i+B*j)%7;
            looked[i][j] = 0;
        }
    }
    int last_2 = 1;
    int last_1 = 1;
    looked[1][1] = 2;
    unsigned long next = n;
    for(unsigned long m=3; m<=next; m++)
    {
        int curr = mat[last_1][last_2];
        last_2 = last_1;
        last_1 = curr;
        if(looked[last_1][last_2] > 0)
        {
            //开始循环了！
            next = (n - looked[last_1][last_2])%(m - looked[last_1][last_2]) + m;
        }
        looked[last_1][last_2] = m;
    }
    return last_1;
}
int main()
{
    int A, B;
    unsigned long n;
    while(cin >> A >> B >> n && A+B+n != 0)
    {
        cout << f(A, B, n) << endl;
    }
    return 0;
}

Leave a Reply Cancel reply