矩阵快速幂模板

 1 struct matrix
 2 {
 3     long long m[3][3];
 4     matrix()
 5     {
 6         memset(m,0,sizeof(m));
 7     }
 8     matrix operator*(const matrix b)const
 9     {
10         long long i,j,k;
11         matrix ans;
12         for(i=0; i<3; i++)
13         {
14             for(j=0; j<3; j++)
15             {
16                 ans.m[i][j]=0;
17                 for(k=0; k<3; k++)
18                 {
19                     ans.m[i][j]+=m[i][k]*b.m[k][j];
20                     ans.m[i][j]%=mod;
21                 }
22             }
23         }
24         return ans;
25     }
26     void set(long long a,long long b)
27     {
28         m[0][0]=a;
29         m[0][1]=b;
30         m[1][0]=1;
31         m[1][1]=0;
32         m[2][0]=1;
33         m[2][1]=0;
34         m[2][2]=1;
35     }
36 } e;
37 long long qpow(long long n,long long f1,long long f2,long long a,long long b)
38 {
39     n--;
40     e.m[0][0]=1;
41     e.m[1][1]=1;
42     e.m[2][2]=1;
43     matrix temp,ans;
44     ans=e;
45     temp.set(a,b);
46     while(n)
47     {
48         if(n&1)
49             ans=ans*temp;
50         temp=temp*temp;
51         n>>=1;
52     }
53     long long fn=(ans.m[1][1]*f1+ans.m[1][0]*f2)%mod;
54     long long sum=(ans.m[2][0]*f2+ans.m[2][1]*f1+ans.m[2][2]*f1)%mod;
55     return fn;
56 }
矩阵快速幂 模板

矩阵快速幂模板
