矩阵快速幂模版

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 #include <math.h>
 7 #include <queue>
 8 #include <set>
 9 
10 #define INF 0x3f3f3f3f
11 #define pii pair<int,int>
12 #define LL long long
13 using namespace std;
14 typedef unsigned long long ull;
15 const int mod = 1000000009;
16 const int N = 10;
17 
18 LL tmp[N][N],res[N][N];
19 
20 void multi(LL a[][N],LL b[][N],int n){
21     memset(tmp,0, sizeof(tmp));
22     for (LL i=0;i<n;i++){
23         for (LL j=0;j<n;j++){
24             for (LL k=0;k<n;k++){
25                 tmp[i][j] += (a[i][k]*b[k][j]) % mod;
26             }
27             tmp[i][j] = tmp[i][j] % mod;
28         }
29     }
30     for (LL i=0;i<n;i++){
31         for (LL j=0;j<n;j++)
32             a[i][j] = tmp[i][j];
33     }
34 }
35 
36 void Pow(LL a[][N],LL m,int n){
37     memset(res,0, sizeof(res));
38     for (LL i=0;i<n;i++){
39         res[i][i] = 1;
40     }
41     while (m){
42         if (m & 1){
43             multi(res,a,n);
44         }
45         multi(a,a,n);
46         m >>= 1;
47     }
48 }
49 LL a[N][N];
50 
51 int main(){
52     LL m;
53     int n;
54     while (~scanf("%lld",&m)){
55         n = 2;
56         a[0][0] = a[0][1] = a[1][0] = 1;
57         a[1][1] = 0;
58         Pow(a,m-1,n);
59         printf("%lld\n",res[0][0]%mod);
60     }
61     return 0;
62 }