• 前言
• 题目大意
• 思路
  • 矩阵性质
    • 结合律
    • 分配律
    • 交换律
  • 本题
• 代码
• 总结

前言

矩阵感觉更多的是套路和规则，只要把套路总结出来题目都是那么几类。

题目大意

给出矩阵 $A$，求 $A^k$。

对于 $100\%$ 的数据，$1\le n \le 100$，$0 \le k \le 10^{12}$，$|A_{i,j}| \le 1000$。

思路

可以把矩阵理解成一个 $n\times m$ 的二维数组。在做题之前可以让我们证一下矩阵乘法的性质。

矩阵性质

结合律

这个律也是用的最多的一个。

$A\times B\times C=A\times (B\times C)$

左边：

$c_{i j} = \sum_{k = 1} a_{i k} b_{k j}$

$ans_{i,j}=\sum_{k=1}(\sum_{l = 1} A_{i l} B_{l k})\times C_{k,j}$

右边：

$c_{i j} = \sum_{k = 1} B_{i k}C_{k j}$

$ans_{i,j}=\sum_{k=1}A_{i,k}\times c_{k,j}$

$ans_{i,j}=\sum_{k=1}A_{i,k}\times (\sum_{l=1}B_{k,l}\times C_{l,j})$

在化一下清楚一点，的出来这两个式子：

$\sum_{k,l}A_{i,l}\times B_{l,k}\times C_{k,j}$

$\sum_{k,l}A_{i,k}\times B_{k,l}\times C_{l,j}$

分配律

挺显然的，不证了。可以理解为加法的话早晚得并乘法。

交换律

也很显然吧。$(n*m)*(m*p)$ 才能做计算，中间两个要相等。交换变成 $(m*p)*(n*m)$ 了，可能不行。

本题

本题就是知道什么是矩阵乘法，做法可以理解为一模一样的快速幂，只不过在计算的时候变量换成了矩阵，乘号换成了重载运算符后的矩阵乘法公式。

代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll MAXN=105;
const ll MOD=1e9+7;
ll n;
struct Matrix{
    ll m[MAXN][MAXN];
    Matrix (){
        memset(m,0,sizeof(m));
    }
    void build(){
        for (int i = 1; i <=n ; ++i) {
            m[i][i]=1;
        }
    }
}a;
Matrix operator *(const Matrix &A,const Matrix &B){
    Matrix C;
    for (int k = 1; k <=n ; ++k) {
        for (int i = 1; i <=n ; ++i) {
            for (int j = 1; j <=n ; ++j) {
                C.m[i][j]+=A.m[i][k]*B.m[k][j];
                C.m[i][j]%=MOD;
            }
        }
    }
    return C;
}
ll k;
int main(){
    scanf("%lld%lld",&n,&k);
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=n ; ++j) {
            scanf("%lld",&a.m[i][j]);
        }
    }
    Matrix ans;
    ans.build();
    while (k){
        if(k&1){
            ans= ans*a;
        }
        k>>=1;
        a=a*a;
    }
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j <=n ; ++j) {
            printf("%lld ",ans.m[i][j]);
        }
        printf("\n");
    }
    return 0;
}

总结

证明了矩阵的分配律和结合律，交换律是错的。主要证明了结合律。