hdu 1005 Number Sequence (矩阵快速幂加速线性递推式)
题意：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).
思路：矩阵加速线性递推式。
这题第一次看是2012年11月2333，当时用pascal写的
1/* ***********************************************
2Author :111qqz
3Created Time :Mon 31 Oct 2016 05:03:40 AM CST
4File Name :code/hdu/1005.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33struct Mat
34{
35 LL mat[2][2];
36 void clear()
37 {
38 ms(mat,0);
39 }
40}M,M1;
41Mat operator * ( Mat a,Mat b)
42{
43 Mat c;
44 c.clear();
45 for ( int i = 0 ;i < 2 ; i ++)
46 for ( int j = 0 ; j < 2 ; j++)
47 for ( int k = 0 ; k < 2 ; k++)
48 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j] )%7;
49 return c;
50}
51Mat operator ^ ( Mat a,LL b)
52{
53 Mat res;
54 res.clear();
55 for ( int i = 0 ; i < 2 ; i++)
56 res.mat[i][i] = 1;
57 while (b>0)
58 {
59 if (b&1) res = res * a;
60 b = b >> 1LL;
61 a = a * a;
62 }
63 return res;
64}
65LL A,B,n;
66void init()
67{
68 M.clear();
69 M.mat[0][1] = 1;
70 M.mat[1][0] = B;
71 M.mat[1][1] = A;
72 M1.clear();
73 M1.mat[0][0] = 1;
74 M1.mat[1][0] = 1;
75}
76int main()
77{
78 #ifndef ONLINE_JUDGE
79 freopen("code/in.txt","r",stdin);
80 #endif
81 while (~scanf("%lld%lld%lld",&A,&B,&n))
82 {
83 init();
84 if (A==0&&B==0&&n==0) break;
85 Mat res = (M^(n-2))*M1;
86 printf("%lld\n",res.mat[1][0]);
87
88 }
89
90 #ifndef ONLINE_JUDGE
91 fclose(stdin);
92 #endif
93 return 0;
94}