hhhh 我复活了!!

最近学了亿一点点东西
慢慢来写吧

先来记录一下矩阵

定义 & 矩阵乘法 & 初等变换

对于矩阵 $A$ ,主对角线指所有 $A_{i,i}$ 的元素

单位矩阵

一般以 $I$ 表示单位矩阵，形式为:

对角矩阵

同型矩阵

两个矩阵，行数与列数对应相同，称为同型矩阵。

方阵

行数等于列数的矩阵称为方阵．方阵是一种特殊的矩阵．对于”$n$ 阶矩阵”的习惯表述，实际上讲的是 $n$ 阶方阵．阶数相同的方阵为同型矩阵。

研究方程组、向量组、矩阵的秩的时候，使用一般的矩阵．研究特征值和特征向量、二次型的时候，使用方阵。

三角矩阵

如果方阵主对角线左下方的元素均为 $0$，称为上三角矩阵．如果方阵主对角线右上方的元素均为 $0$，称为下三角矩阵．

两个上（下）三角矩阵的乘积仍然是上（下）三角矩阵．如果对角线元素均非 0，则上（下）三角矩阵可逆，逆也是上（下）三角矩阵．

单位三角矩阵

如果上三角矩阵 $A$ 的对角线全为 $1$，则称 $A$ 是单位上三角矩阵．如果下三角矩阵 $A$ 的对角线全为 $1$，则称 $A$是单位下三角矩阵．

两个单位上（下）三角矩阵的乘积仍然是单位上（下）三角矩阵，单位上（下）三角矩阵的逆也是单位上（下）三角矩阵．

矩阵乘法

矩阵乘法是 向量内积 的推广。
矩阵相乘只有在第一个矩阵行数等于第二个矩阵的列数是才有意义。

设 $A$ 为 $p \times m$ 的矩阵，$B$ 为 $m \times q$ 的矩阵。
设 $C=A\times B$ ，则 $C$ 为 $p\times q$ 的矩阵。
其中 $C$ 的第 $i$ 行第 $j$ 列的元素 $C_{i,j}$ 表示为：

容易证明，矩阵乘法不满足一般的交换律，满足结合律。

初等矩阵

倍乘矩阵

倍乘矩阵是一种特殊的对角矩阵。

其中第 $i$ 个元素为 $k \ (k\not = 0)$

特别的，当$k=1$时，$D_i(k)=I$

对换矩阵

对换矩阵是一种特殊的的对称矩阵。

对换矩阵主对角线上除了第 $i$ 个元素和第 $j$ 个元素都为 $1$，第 $i$ 个元素和第 $j$ 个元素为 $0$ ，而在第 $i$ 行第 $j$ 列和第 $j$ 行第 $i$ 列为 $1$，其余位置为 $0$。

对换矩阵要求 $i$ 与 $j$ 不能相等．

倍加矩阵

倍加矩阵是在单位阵 $I$ 的基础上，令第 $i$ 行第 $j$ 列为 $k$ 。

倍加矩阵要求  $i \not = j$ 。

倍加矩阵是一种上三角矩阵或者下三角矩阵．

初等变换

不仅限于方阵，对于一般的矩阵 $A$，可以进行初等行变换和初等列变换，统称为初等变换。

初等行变换与初等列变换一样，都有 3 种：

• 倍乘（multiplication）
• 对换（switching）
• 倍加（addition）

这里先介绍初等行变换：

• 第 𝑖 行乘非零数 $k$ ：$B\to D_{i}(k)B$
• 第 𝑖，𝑗 行互换：$B\to P_{i,j}B$
• 第 𝑗 行乘 𝑘 加到第 𝑖 行：$B\to T_{i,j}(k)B$

将上述操作的行改为列，即得到初等列变换。

矩阵快速幂

对于矩阵 $A$ ，显然 $A^n$ 中 $n$ 可以被拆分成唯一分解 $n=p_0+p_12^1+p_22^2+\dots+p_k2^k$ ，其中 $p_i(0\le i \le k) \in [0,1]$ 且 $p_k\not=0$

所以对于所有不为 $0$ 的 $p_i$ 的 $i$ 的集合 $P$ ，$A^n=\sum _{i \in P} A^{2^i}$

容易发现，这正是快速幂。
故我们可以用快速幂加速矩阵幂运算

例题：P3390 【模板】矩阵快速幂

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc mod=1e9+7;
intc N=200;
class Matrix {
    public:
    int line,col;
    int c[N][N];
    Matrix ()=default;
    Matrix (int n,int m):line(n),col(m) {
        memset (c,0,sizeof c);
    } 
    static Matrix unit (int n) {
        Matrix m=Matrix(n,n);
        for (int i=1;i<=n;i++) m.c[i][i]=1;
        return m;
    }
    int * operator [] (const int pos) {
        return c[pos];
    }
    Matrix operator * (Matrix &q) {
        Matrix ans=Matrix(line,q.col);
        for (int i=1;i<=ans.line;i++) {
            for (int j=1;j<=ans.col;j++) {
                for (int k=1;k<=col;k++) ans[i][j]=(ans[i][j]+c[i][k]*q[k][j])%mod;
            }
        }
        return ans;
    }
    Matrix pow (int b) {
        Matrix res=Matrix::unit(line),a=*this;
        if (b<=0) return res;
        while (b) {
            if (b&1) res=res*a;
            a=a*a;
            b>>=1;
        }
        return res;
    }
};
int n,k;
signed main() {
    cin>>n>>k;
    Matrix mx=Matrix(n,n);
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) cin>>mx[i][j];
    }
    mx=mx.pow(k);
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) cout<<mx[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc mod=1e9+7;
intc N=200;
class Matrix {
    public:
    int line,col;
    int c[N][N];
    Matrix ()=default;
    Matrix (int n,int m):line(n),col(m) {
        memset (c,0,sizeof c);
    } 
    static Matrix unit (int n) {
        Matrix m=Matrix(n,n);
        for (int i=1;i<=n;i++) m.c[i][i]=1;
        return m;
    }
    int * operator [] (const int pos) {
        return c[pos];
    }
    Matrix operator * (Matrix &q) {
        Matrix ans=Matrix(line,q.col);
        for (int i=1;i<=ans.line;i++) {
            for (int j=1;j<=ans.col;j++) {
                for (int k=1;k<=col;k++) ans[i][j]=(ans[i][j]+c[i][k]*q[k][j])%mod;
            }
        }
        return ans;
    }
    Matrix pow (int b) {
        Matrix res=Matrix::unit(line),a=*this;
        if (b<=0) return res;
        while (b) {
            if (b&1) res=res*a;
            a=a*a;
            b>>=1;
        }
        return res;
    }
};
int n,k;
signed main() {
    cin>>n>>k;
    Matrix mx=Matrix(n,n);
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) cin>>mx[i][j];
    }
    mx=mx.pow(k);
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) cout<<mx[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}