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;
}