一、基础知识
1、矩阵的定义
2、行矩阵和列矩阵应该比较好理解,就是一个矩阵的每一行都可以称之为一个行矩阵,同理列矩阵也一样。
3、同型矩阵:设有矩阵A和矩阵B,矩阵A的行数和列数都与矩阵B的相同,则矩阵A、B是同型矩阵
像图中这样就是两个同型矩阵
4、单位矩阵
在矩阵的乘法中,有一种矩阵起着特殊的作用,如同数的乘法中的1,这种矩阵被称为单位矩阵.
它是个方阵,从左上角到右下角的对角线(称为主对角线)上的元素均为1。除此以外全都为0。
二、矩阵的相关运算
1、矩阵加法
图上说的也很清楚了吧,矩阵加法满足加法交换律和加法结合律。
2、矩阵乘法
其中,c[i][j]表示:矩阵A的第 i 行与矩阵B的第 j 列的对应乘积的和。
2、矩阵快速幂引入
为了引出矩阵快速幂,我们先来学整数快速幂,加入我们要计算如果现在要算X^8:则 XXXXXXXX 按照寻常思路,一个一个往上面乘,则乘法运算进行7次。
XX)XX)XX)XX)
这种求法,先进行乘法得X2,然后对X2再执行三次乘法,这样去计算,则乘法运算执行4次。已经比七次要少。所以为了快速算的整数幂,就会考虑这种结合的思想。
现在要考虑应该怎么分让计算比较快。接下来计算整数快速幂。例如:X^19次方。
19的二进制为:1 0 0 1 1 。
由Xm)Xn) = X^m+n)
则X^19 = X16)X2)*X^1)
那么怎么来求解快速幂呢。请看下列代码:
求解X^N的值。
int quickpowint x,int N){
int res = x;
int ans = 1;
whileN){
ifN & 1){
ans = ans * res;
}
res = res * res;
N = N >> 1;
}
return ans;
}
那现在,我们来仔细看一下这个代码。
对于x^19来说,19的二进制是1 0 0 1 1
初始化
ans = 1; res = x;
因为19的二进制最后一位是 1 ,所以19是奇数。
ans = res * ans = x ;
res = res * res = x ^ 2;
然后右移一位,就变成了1 0 0 1
则最后一位是 1 ,所以是奇数。
ans = ans * res
= x * x ^ 2) = x ^ 3;
res = res * res
= x ^ 2 * x ^ 2
= x ^ 4;
然后右移一位,变成了1 0 0
则最后一位是 0 ,所以是偶数。
res = res * res
= x ^ 4 * x ^ 4
= x ^ 8;
然后右移一位,变成了1 0
则最后一位是偶数。
res = res * res
= x ^ 8 * x ^ 8
= x ^ 16;
然后右移一位,只剩下 1 了。
还看吗?肯定是奇数
ans = ans * res
= x ^ 3) *(x ^ 16)
= x ^ 19
res = res * res = x ^ 32
总结一下:
从上述叙述中可以看出res = x ^ m
始终是与二进制位置上的权值是相对应的。
当二进制位是 0 时 , 我们只让res ^ 2,来对应二进制下一位的权值
当二进制位是 1 时 , ans = ans * res , 再使res ^ 2
说了一大堆,我们进入正题,矩阵快速幂
假如现在有一个n * n的方阵A。给出一个数M,让算矩阵A的M次幂,A ^ M.则上面代码可以化为。
struct matrix{
int m[maxn][maxn];
}ans , res;//这是计算矩阵乘法的参数
//我们假设参数矩阵是 A 、B和一个数n表示n * n)
matrix mulmatrix A,matrix B){
matrix tmp;
//这是我们临时设置的一个矩阵,存A*B的结果
forint i=1;i<=n;i++)
forint j=1;j<=n;j++)
tmp.m[i][j] = 0;
forint i=1;i<=n;i++)
forint j=1;j<=n;j++)
forint k=1;k<=n;k++)
tmp.m[i][j] += A.m[i][k] * B.m[k][j];
return tmp;
}
//快速幂算法,求矩阵res的N次幂
matrix quickpowermatrix res,int x){
/*我们在上面介绍整数幂的时候将ans初始化为 1
但对于矩阵乘法来说,ans应该初始化为单位矩阵
现在补充一个单位矩阵的性质:
单位矩阵乘任意矩阵都是原矩阵
*/
forint i=1;i<=n;i++)//单位矩阵定义方法
forint j=1;j<=n;j++){
ifi == j) ans.m[i][j] = 1;
else ans.m[i][j] = 0;
}
whilex){
ifx & 1)
ans = mulans , res);
res = mulres , res);
x = x >> 1;
}
}
贴上一个完整的代码吧:
P3390 矩阵快速幂模板
#include <cstdio>
#include <istream>
#include <cstring>
#include <algorithm>
#include <cmath>//pow函数,其实没啥用
using namespace std;
const int mod = pow10,9)+7;
long long n,k;
struct matrix{
long long m[105][105];
}ans , res;
matrix mulmatrix x,matrix y){
matrix tmp;
forint i=1;i<=n;i++)
forint j=1;j<=n;j++)
tmp.m[i][j] = 0;
forint i=1;i<=n;i++)
forint j=1;j<=n;j++)
forint k=1;k<=n;k++)
tmp.m[i][j] = tmp.m[i][j] % mod + x.m[i][k] * y.m[k][j]) % mod;
return tmp;
}
matrix quickpowermatrix res,long long k){
forint i=1;i<=n;i++)
forint j=1;j<=n;j++){
ifi == j) ans.m[i][j] = 1;
else ans.m[i][j] = 0;
}
whilek){
ifk & 1)
ans = mulans , res);
res = mulres , res);
k = k >> 1;
}
return ans;
}
int main){
scanf"%lld%lld",&n,&k);
forint i=1;i<=n;i++){
forint j=1;j<=n;j++)
scanf"%lld",&res.m[i][j]);
}
ans = quickpowerres , k);
forint i=1;i<=n;i++){
forint j=1;j<=n;j++)
printf"%lld ",ans.m[i][j] % mod);
printf"
");
}
return 0;
}
当然,矩阵快速幂还有另一种写法,用重载运算符重载 * 嘛
代码我就不解释了
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 110;
const int MOD = 1e9 + 7;
ll n,k;
struct martix {
ll a[N][N];
martix operator*const martix &b) const {
martix x;
forint i = 1 ; i <= n ; i++) {
forint j = 1 ; j <= n ; j++) {
x.a[i][j] = 0;
forint k = 1 ; k <= n ; k++) {
x.a[i][j] += a[i][k] * b.a[k][j];
x.a[i][j] %= MOD;
}
}
}
return x;
}
}mart;
martix quick_powmartix x,ll y) {
martix ans = x,s = x;
for ; y ; y >>= 1) {
ify & 1) ans=ans * s;
s = s * s;
}
return ans;
}
int main) {
scanf"%lld%lld",&n,&k);
forint i = 1 ; i <= n ; i++) {
forint j = 1 ; j <= n ; j ++) {
scanf"%lld",&mart.a[i][j]);
}
}
mart = quick_powmart,k - 1);
forint i = 1 ; i <= n ; i++) {
forint j = 1 ; j <= n ; j ++)
printf"%lld ",mart.a[i][j]);
printf"
");
}
return 0;
}
上面只是简单的计算矩阵的幂,可能会感觉很抽象,因为上述矩阵并没有具体的含义,
现在就举例说明矩阵快速幂在实际运用中的意义:
以最常见的斐波那契数列为例:众所周知:斐波那契数列递推公式为:
F[n] = F[n-1] + F[n-2].
由f[0]=0,f[1]=1,可以递推后面的所有数。
在以前,我们会常常用for循环,这是最直接的算法。
但是,n 等于十亿你该怎么用for循环呢。。
好吧,在介绍矩阵快速幂,肯定是用矩阵快速幂来写。。
顺风不浪,逆风不怂。