矩阵快速幂模板

 1 #define mod 1000000007
 2 typedef long long ll;
 3 #define MAX 105
 4 const int N=3;//矩阵的大小
 5 int T;
 6 ll n;
 7 struct hh
 8 {
 9     ll ma[N][N];
10 }a,res;
11 hh multi(hh a,hh b)
12 {
13     hh tmp;
14     memset(tmp.ma,0,sizeof(tmp.ma));
15     for(int i=0;i<N;i++)
16         for(int j=0;j<N;j++)
17             for(int k=0;k<N;k++)
18         {
19             tmp.ma[i][j]=add(tmp.ma[i][j],a.ma[i][k]*b.ma[k][j]);
20         }
21    return tmp;
22 }
23 void fast_pow(hh a,long long k)
24 {
25     memset(res.ma,0,sizeof(res.ma));
26     for(int i=0;i<N;i++)res.ma[i][i]=1;
27     while(k>0)
28     {
29         if(k&1) res=multi(res,a);
30         a=multi(a,a);
31         k>>=1;
32     }
33 }