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