题目链接
关于矩阵快速幂
矩阵定义
由(n×m)个数(a[i][j])排成的(n)行(m)列的数表称为(n)行(m)列的矩阵，简称(n×m)矩阵。
矩阵加法
只有行列均相同的矩阵才有加法
运算也比较简单，把对应位置的数相加得到一个新的矩阵，即为答案
[egin{bmatrix} 1 & 1 & 2 \ 1 & 0 & 1 end{bmatrix} + egin{bmatrix} 2 & 3 & 3 \ 3 & 3 & 2 end{bmatrix} = egin{bmatrix} 3 & 4 & 5 \ 4 & 3 & 3 end{bmatrix}
]
加法运算律：
[A + B = B + A
]
[(A + B) + C = A + (B + C)
]
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[101][101], x, i, j;
int n, m;
cin >> n >> m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin >> a[i][j];
for(i=0;i<n;i++)
for(j=0;j<m;j++){
cin >> x;
a[i][j] += x;
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cout << a[i][j] << " ";
}
cout << endl;
}
}
重载运算符的以后会在总结篇里给出...咕咕咕咕
矩阵减法
和上面一样，把+换成-
矩阵乘法
前提条件:
一个矩阵的行数等于另一个矩阵的列数
也就是若A是(i×j)的矩阵，那么B必须是(j×i)的矩阵(对称的)
公式：
[C_{ij} = sum_{i = 1}^n A_{ik} * B_{kj}
]
注意此处求解时的循环顺序应为：
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
t.m[i][j]=0;
for(int k=0;k<n;++k)
{
t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
}
}
想知道为什么？
因为一些缓存问题，请看luogu日报
例子：
[egin{bmatrix} 1 & 2\ 2 & 3 end{bmatrix} imes egin{bmatrix} 2 & 4 & 5 \ 3 & 4 & 3 end{bmatrix} = egin{bmatrix} 8 & 12 & 11 \ 13 & 20 & 19 end{bmatrix}
]
运算规律
无交换律
乘法满足结合律，左分配律，右分配律，即
[(A imes B) imes C = A imes (B imes C)
]
[(A + B) imes C = A imes C + B imes C)
]
[C(A + B) = C imes A + C imes B
]
矩阵快速幂
就是把普通的快速幂的*换成了矩阵乘法
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
#define MAXN 105
#define mod 1000000007
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
ll n,k;
struct matrix
{
ll m[105][105];
}a;
/*乘法*/
matrix cheng(matrix a,matrix b)
{
matrix t;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
t.m[i][j]=0;
for(int k=0;k<n;++k)
{
t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
}
}
return t;
}
/*快速幂*/
matrix quick_pow(matrix a,ll k)
{
matrix ret=a,b=a;
k--;
while(k)
{
if(k&1) ret=cheng(b,ret);
b=cheng(b,b);
k>>=1;
}
return ret;
}
/*读人*/
int main()
{
cin>>n>>k;
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
cin>>a.m[i][j];
}
}
a=quick_pow(a,k);
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
cout<<a.m[i][j]<<" ";
}
cout<<'
';
}
return 0;
}