矩阵快速幂

一、基础知识

1.矩阵乘法

设A为的矩阵，B为的矩阵，那么称的矩阵C为矩阵A与B的乘积，记作，其中矩阵C中的第行第列元素可以表示为：

 1 typedef long long ll;
 2 const int Mod=10000;
 3 struct mat{
 4     ll a[2][2];
 5 };
 6 mat mat_mul(mat x,mat y){
 7     mat ans;
 8     memset(ans.a,0,sizeof(ans.a));
 9     for (int i=0;i<2;i++){
10         for (int j=0;j<2;j++)
11         for (int k=0;k<2;k++)
12             ans.a[i][j]=ans.a[i][j]+(x.a[i][k]*y.a[k][j])%Mod;
13     }
14     return ans;
15 }

2.矩阵快速幂

顾名思义，就是将数字的幂运算变成矩阵的幂运算。orz...直接上代码就好。

 1 mat mat_mul(mat &x,mat &y,int Mod){
 2     mat ans;
 3     memset(ans.a,0,sizeof(ans.a));
 4     for (int i=0;i<2*n;i++)
 5         for (int j=0;j<2*n;j++)
 6         for (int kk=0;kk<2*n;kk++){
 7             ans.a[i][j]+=x.a[i][kk]*y.a[kk][j];
 8             ans.a[i][j]%=Mod;
 9         }
10     return ans;
11 }
12 void mat_pow(mat &res,int k,int Mod){
13     mat c=res;
14     k--;
15     while (k){
16         if (k&1) res=mat_mul(res,c,m);
17         k>>=1;
18         c=mat_mul(c,c,m);
19     }
20 }

二、应用（例题）

3.poj3233