有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给出A，B和N，求f(n)的值。
Input
输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)Output
输出f(n)的值。Input示例
3 -1 5Output示例
6
首先说矩阵乘法，正方形矩阵，行数、列数都为N，a[i][j] = (k 1->N) a[i][k]* a[k][j] 。
f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7
2*2 矩阵X： A B 乘 矩阵Y f(2) 0 等于 f(3) 0
1 0 f(1) 0 f(2) 0
可得 X^(N-2) * Y = f(n) 0 注意 X， Y 为矩阵
f(n-1) 0
在计算 X^(N-2) 是要用到矩阵快速幂，矩阵快速幂和 快速幂 的思路差不多， 只不多将两个数的乘法换成矩阵乘法。
注意：这道题有一个隐藏的坑点，就是序列中的数需要大于等于 0
#include <iostream>
#include <cstring>
using namespace std;const int N = 2;
const int mod = 7;typedef struct matrix{int a[N][N];
}Matrix;Matrix multi(Matrix A, Matrix B) {Matrix temp;memset(temp.a, 0, sizeof(temp.a));for(int i=0; i<N; i++)for(int j=0; j<N; j++)for(int k=0; k<N; k++) {temp.a[i][j] += A.a[i][k]*B.a[k][j];temp.a[i][j] %= mod;}return temp;
}Matrix quick_multi(Matrix A, int n) {Matrix temp;memset(temp.a, 0, sizeof(temp));for(int i=0; i<N; i++) temp.a[i][i] = 1;while(n) {if(n&1)temp = multi(temp, A);A = multi(A, A);n >>= 1;}return temp;
}int main(){int A, B, K;cin >> A >> B >> K;if(K < 2) {cout << "1" << endl;return 0;}Matrix X, Y;X.a[0][0] = (A%mod+mod)%mod, X.a[0][1] = (B%mod+mod)%mod;X.a[1][0] = 1, X.a[1][1] = 0;Y.a[0][0] = 1, Y.a[0][1] = 0;Y.a[1][0] = 1, Y.a[1][1] = 0;Matrix ans = quick_multi(X, K-2);ans = multi(ans, Y);cout << ((ans.a[0][0]%mod)+mod)%mod << endl;return 0;
}