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.
题解
题目大意：
题目意思很好理解，给你一个类似于fabonacci数列的关系式，要求这个数列的第n项。但是注意n的范围，如果直接用数组模拟的话，可能会栈溢出。所以就需要去寻找规律，找到一个周期，这是一个思路。还有一个思路，就是将迭代式转化为矩阵乘法，取模运算，可以用快速幂算法进行优化，这种思路也很巧妙。
矩阵乘法：
迭代式为：f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7
可以将迭代式转化为矩阵乘法形式：
$$
\begin{bmatrix}
f(n)\
f(n-1)\
\end{bmatrix}
= \begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}
\begin{bmatrix}
f(n-1)\
f(n-2)\
\end{bmatrix}
$$
$$
\begin{bmatrix}
f(n-1)\
f(n-2)\
\end{bmatrix}
= \begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}
\begin{bmatrix}
f(n-2)\
f(n-3)\
\end{bmatrix}
$$
$$
\begin{bmatrix}
f(n)\
f(n-1)\
\end{bmatrix}
= \begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}
\begin{bmatrix}
1 & 1\
1 & 0\
\end{bmatrix}
\begin{bmatrix}
f(n-2)\
f(n-3)\
\end{bmatrix}
$$
题中的迭代式可转化为：
$$
\begin{bmatrix}
f(n)\
f(n-1)\
\end{bmatrix}
= \begin{bmatrix}
A & B\
1 & 0\
\end{bmatrix}
\begin{bmatrix}
f(n-1)\
f(n-2)\
\end{bmatrix}
$$
初始条件是f(1) = 1, f(2) = 1,也就转化为求中间矩阵的n-2次方，可以通过快速幂算法来处理幂运算，关于快速幂算法可以参看快速幂。
$$
\begin{bmatrix}
f(n)\
f(n-1)\
\end{bmatrix}
= \begin{bmatrix}
A & B\
1 & 0\
\end{bmatrix}^{(n-2)}
\begin{bmatrix}
f(2)\
f(1)\
\end{bmatrix}
$$
实现代码如下：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
using namespace std;
const int m = 2;
const int mod = 7;
struct Matrix
{
int x[m][m];
};
// 矩阵乘法
Matrix multiplication(Matrix a, Matrix b)
{
Matrix temp;
memset(temp.x, 0, sizeof(temp.x));
for(int i=0; i<m; i++)
{
for(int j=0; j<m; j++)
{
for(int k=0; k<m; k++)
{
temp.x[i][j] += a.x[i][k] * b.x[k][j];
temp.x[i][j] %= mod;
}
}
}
return temp;
}
//矩阵的快速幂
Matrix powmatrix(Matrix matrix, int n)
{
Matrix temp;
memset(temp.x, 0, sizeof(temp.x));
for(int i=0; i<m; i++)
temp.x[i][i] = 1; //初始化为单位阵
while(n)
{
if(n%2 == 1)
{
temp = multiplication(temp, matrix);
}
matrix = multiplication(matrix, matrix);
n = n/2;
}
return temp;
}
int main()
{
int A, B;
long long n;
while((cin>>A>>B>>n) && A!=0 && B!=0 && n!=0)
{
Matrix mat;
// 初始条件
mat.x[0][0] = A;
mat.x[0][1] = B;
mat.x[1][0] = 1;
mat.x[1][1] = 0;
mat = powmatrix(mat, n-2);
printf("%d\n",(mat.x[0][0] + mat.x[0][1])%mod);
}
return 0;
}
找规律：
题目给的n的范围比较大，所以要想到去找规律，寻找一个周期出来，然后再通过周期进行处理；题目给的迭代式是mod 7，mod 7的结果最多只有（0,1,2,3,4,5,6）7种，两个mod 7的数组合最多就是7*7=49种，所以循环节最多为49。然后再通过循环找到周期。
1 |
|
参考链接：
https://blog.csdn.net/qq_27508477/article/details/47663185
https://blog.csdn.net/rocklee_1227/article/details/7997659