HDU-1005 Number Sequence

HDU-1005 Number Sequence

/ 0评 / 973次 / 5

Description

A number sequence is defined as follows:

\( f(1) = 1 \)

\( f(2) = 1 \)

\( f(n) = (A * f(n - 1) + B * f(n - 2)) \%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.

题目翻译

一个序列

\( f(1) = 1 \)

\( f(2) = 1 \)

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

现给你a, b, n, 请计算出 \( f(n) \) 的值。

Analysis

本题看上去要求并不复杂,求一个递推数列而已,但是数据量很大,本蒟蒻一开始想都没想写了个水方法,结果MLE

回过头看题目,发现数列当中的任一项都必然是0到6之间的任意一个数,数的情况是有限的,也就意味着循环是在所难免的,因为7*7总共也就49种情况,不可能会有更长的循环节

也就是说去搜取一个数列当中的最短循环节即可。

但是问题接踵而来,循环节的标记位点的选择成为一个重点。显然,任何一个数都是由前两个数递推而得,那么也就意味着循环节的标记位点可以选择成相邻两项。

一开始我选择了一开始的 \( fib[1]=1 \) 以及 \( fib[2]=1 \),可是WA了

问题出在(比如说)这组数据 247 602 35363857

演算可知,他的循环是从第三个数开始的,而原因就是出在 \( fib[2]=1 \) ,他的来源并不明确,是人为规定的,也就是说这样的一个递推是从一开始就理论不完备的

因此,我们将循环节的标记位点选择为严格满足递推关系的 \( fib[3] \) 以及 \( fib[4] \) 就可以解决问题

Accepted Code

/*
 * @Author: Gehrychiang
 * @Date: 2020-02-04 11:37:56
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;
int fib[105];
int main()
{
    memset(fib, 0, sizeof(fib));
    fib[0] = 0;
    fib[1] = 1;
    fib[2] = 1;
    int a, b, n;
    while (cin >> a >> b >> n)
    {
        if (a == 0 && b == 0 && n == 0)
            break;
        fib[3] = (a * fib[2] + b * fib[1]) % 7;
        fib[4] = (a * fib[3] + b * fib[2]) % 7;
        int i;
        for (i = 5; i <= 60; i++)
        {
            fib[i] = (a * fib[i - 1] + b * fib[i - 2]) % 7;
            if (fib[i] == fib[4] && fib[i - 1] == fib[3])
            {
                break;
            }
        }
        //显然也就是从1到i-2循环
        int xunhuanchangdu = i - 4;
        if (n == 1 || n == 2)//如果为前两个,直接输出
        {
            cout << "1" << endl;
        }
        else if ((n - 2) % xunhuanchangdu == 0)//如果结果为一次循环的末尾则输出末尾即可,不加这句就会输出fib[2]
        {
            cout << fib[xunhuanchangdu + 2] << endl;
        }
        else//正常输出,n-2是扣掉前面的fib[1]和fib[1],而+2也是补上前面的空
        {
            cout << fib[(n - 2) % xunhuanchangdu + 2] << endl;
        }
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.59615