矩阵快速幂

最近刷了一下斐波那契数的题，学了一下矩阵快速幂，做一下总结。

首先在学矩阵快速幂之前，有一些必须要掌握的知识。

1）矩阵的乘法（详细介绍请参考百度百科）

　　其中的c[i, j]是a矩阵中的第i行与b矩阵中第j列的乘积和。

　　例：

　　所以说可以写成是。

　　用代码实现就是

1 void mult(int First_Matrix[N][N], int Second_Matrix[N][N])
2 {
3     int Third_Matrix[N][N];
4     memset(Third_Matrix, 0, sizeof Third_Matrix);
5     for(int i=0;i<N;i++)
6         for(int j=0;j<N;j++)
7             for(int k=0;k<N;k++)
8                 Third_Matrix[i][j] += First_Matrix[i][k]*Second_Matrix[k][j];
9 }

View Code

2）快速乘法和快速幂

　　a*b

　　　快速乘法就是用了2进制和乘法分配律。5==（0101）₂ ，所以7*5 == 7*（0101）₂ ，又可以通过乘法分配律变成 7*（0100+0001）₂ == 7*（4+1）₁₀ 。

　　　　所以就可以通过判断当前位置是不是1位，来判断是否要求和。每一次移动到下一位时，base*2；

 1 int qmult(int a, int b)//a*b
 2 {
 3     int ans = 0;
 4     int base = a;
 5     while(b){
 6         if(b&1)     ans += base;//当前位置是1
 7         b>>=1;//b向右移动一位
 8         base <<= 1;//base *= 2;
 9     }
10     return ans;
11 }

View Code

　 a^b

　　　快速幂与快速乘法差不多，只是把+换做*。

　　　　7^5==7^（0101）₂ =7^（0100 + 0001）₂== 7⁴ * 7¹。（不难发现指数是2ⁿ）

　　　　我们就可以得到快速幂的代码

 1 int qpow(int a, int b)//a^b
 2 {
 3     int ans = 1;
 4     int base = a;
 5     while(b)
 6     {
 7         if(b&1)     ans *= base;
 8         b >>=1;
 9         base = base * base;
10     }
11     return ans;
12 }

View Code

——————————————————————————————————我是分界线———————————————————————————————————————

而矩阵快速幂其实就是快速幂的升级版本。把a_数^b 升级成 a_矩阵^b。

 1 struct Matrix
 2 {
 3     LL c[maxn][maxn];
 4 };//Matrix 矩阵
 5 Matrix mult(Matrix a, Matrix b, int n)//矩阵乘法
 6 {
 7      Matrix hh={0};
 8      for(int i=0;i<n;i++)
 9         for(int j =0;j<n;j++)
10             for(int k = 0;k<n;k++){
11                 hh.c[i][j] += (a.c[i][k]*b.c[k][j])%mod;
12                 hh.c[i][j] %= mod;
13             }
14     return hh;
15 }
16 Matrix qpow_Matrix(Matrix a, int b, int n)
17 {
18     Matrix base = a;
19     Matrix ans;
20     //初始化ans = 1。
21     for(int i =0;i<n;i++)
22         for(int j =0;j<n;j++)
23             if(i==j)    ans.c[i][j] = 1;
24             else ans.c[i][j] = 0;
25     //
26     while(b){
27         if(b&1)     ans = mult(ans, base, n);
28         base = mult(base, base, n);
29         b>>=1;
30     }
31     return ans;
32 }

其中的ans初始化：因为在a^b中ans=1，而在矩阵中要使矩阵ans的对角线为1其他的全部为0（i==j时值为1）才能使 ans_矩阵*b_矩阵=b_矩阵。

贴上练习的题目

1）矩阵乘法：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1137

2）矩阵快速幂：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1113

一题详细的讲构造矩阵的题目

http://www.cnblogs.com/denghaiquan/p/7231022.html