51nod1126(矩阵快速幂)

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1126

题意：中文题诶～

思路：构造矩阵：

（ 0, 1 )^n-1 * ( f0, f1 )

( b, a ) ( f1, f2 )

代码：

 1 #include <bits/stdc++.h>
 2 #define mod 7
 3 #define MAXN 2
 4 using namespace std;
 5 
 6 struct Matrix{
 7     int gg[MAXN][MAXN];
 8 };
 9 
10 Matrix x;
11 Matrix temp={0, 1, 1, 1};
12 Matrix ans={1, 0, 0, 1};
13 
14 Matrix multi(Matrix a, Matrix b){
15     Matrix c;
16     memset(c.gg, 0, sizeof(c.gg));
17     for(int i=0; i<MAXN; i++){
18         for(int j=0; j<MAXN; j++){
19             for(int k=0; k<MAXN; k++){
20                 c.gg[i][j]+=a.gg[i][k]*b.gg[k][j]%mod;
21             }
22             c.gg[i][j]=(c.gg[i][j]+mod)%mod;
23         }
24     }
25     return c;
26 }
27 
28 int get_pow(int n){
29     while(n){
30         if(n&1){
31             ans=multi(ans, x);
32         }
33         x=multi(x, x);
34         n>>=1;
35     }
36     ans=multi(ans, temp);
37     return (ans.gg[0][1]%mod+mod)%mod;
38 }
39 
40 int main(void){
41     int a, b, n;
42     cin >> a >> b >> n;
43     x.gg[0][0]=0, x.gg[0][1]=1, x.gg[1][0]=b, x.gg[1][1]=a;
44     cout << get_pow(n-1) << endl;
45 }