Number Sequence
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
Author
CHEN, Shunbao
Source
ZJCPC2004
题目类型：循环节
算法分析：由于n比较大，直接使用矩阵快速幂会TLE。这里发现所有的序列的循环节的长度都是48，所以可以直接预打出前48个数的表，然后直接查表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 66 + 6; int ans[maxn]; int main() { // ifstream cin ("aaa.txt"); // freopen ("aaa.txt", "r", stdin); long long a, b, n; while (scanf ("%lld%lld%lld", &a, &b, &n) != EOF) { if (a == 0 && b == 0 && n == 0) break; ans[1] = ans[2] = 1; for (int i = 3; i <= 66; i++) { ans[i] = (a * ans[i-1] + b * ans[i-2]) % MOD; } int temp = n % 48; if (temp == 0) cout << ans[48] << endl; else cout << ans[temp] << endl; // cout << ans[49] << " " << ans[50] << " " << ans[51] << endl; } return 0; } |