矩阵基础

矩阵是线性代数中一个非常重要的内容，也是 NOIP 的考点之一。

定义

对于矩阵 \(A\)，主对角线是指 \(A_{i,i}\) 的元素。

0元：所有位置均为 0 的矩阵。

1元（单位矩阵）：主对角线上为 1，其余位置为 0 的矩阵。

单位矩阵之所以是主对角线，是因为一个矩阵在乘上单位矩阵之后是它本身，这就符合我们在学数的基本运算时，一个数乘它本身等于它本身。

实现代码：

struct mat//定义一个矩阵
{
    int v[maxn][maxn];//v[i][j]表示矩阵第 i 行第 j 列的元素
    int n;
    mat(){memset(v,0,sizeof(v));}//初始化一个空矩阵为0元
    mat(int N,int one=0)//初始化矩阵的大小并定义1元。
    {
        n=N;memset(v,0,sizeof(v));
        if(one)for(int i=1;i<=n;i++)v[i][i]=1;//如果定义了单位矩阵，则将主对角线初始化为1。
    }
};

运算

加法/减法

矩阵的加法/减法定义为把两个矩阵对应位置上的数相加减，即 \(C=A \pm B \Leftrightarrow \forall i \in [1,n],\forall j \in [1,m],C_{i,j} = A_{i,j} \pm B_{i,j}\)，其中 \(A,B,C\) 都是 \(n \times m\) 矩阵。

乘法

设 \(A\) 是 \(n \times m\) 矩阵，\(B\) 是 \(m \times p\) 矩阵，则 \(C=A \times B\) 是 \(n \times p\) 矩阵，并且对于 \(\forall i \in [1,n],\forall j \in [1,p]\)：

条件：参与矩阵运算的第一个矩阵的列数必须等于第二个矩阵的行数。

所以结果矩阵 \(C\) 的第 \(i\) 行第 \(j\) 列的数，是由矩阵 \(A\) 的第 \(i\) 行的 \(m\) 个数与矩阵 \(B\) 的第 \(j\) 列的 \(m\) 个数分别相乘再相加得到。

代码实现：

mat operator*(mat A,mat B)//利用重载运算符重载矩阵乘法
{
    mat C=mat(A.n);//C表示 A*B 的结果，由于这里A和B都是方阵，所以结果矩阵的大小和A的大小相同。
    //注意：如果A和B并非方阵，则不能这么定义，而是应该定义为A的行数乘B的列数。
    for(int i=1;i<=C.n;i++)
    for(int j=1;j<=C.n;j++)
    for(int k=1;k<=C.n;k++)
        (C.v[i][j]+=A.v[i][k]*B.v[k][j])%=mod;    
    return C;      
}

运算律

矩阵乘法不满足交换律，因为对于矩阵 \(A\) 和 \(B\)，\(p \ne n\)。

满足结合律，即 \((A \times B) \times C=A \times (B \times C)\)。

满足分配律，即 \((A+B) \times C=A \times C + B \times C\)。

我们可以利用矩阵的结合律，来实现矩阵快速幂。

矩阵快速幂

问题模型：对于一个矩阵 \(A\)，求它的 \(k\) 次幂的结果，即 \(A^k\)。

首先很容易想到一个 \(O(k)\) 的做法——暴力模拟。

是否有优化做法呢？

联想到我们学习快速幂的做法，能否同样运用到矩阵中去呢？

答案是肯定的。

我们可以发现，矩阵中的快速幂其实和数中的快速幂完全一样。因为矩阵的性质和数的性质具有相似性。

实现代码：

int qpow(mat A,int T)
{
    mat ret=mat(A.n,1);//在普通快速幂中我们是初始化为1，这里初始化为单位矩阵。
    while(T)
    {
        if(T&1)ret=ret*A;
        A=A*A;T>>=1;
    }
    return ret;
}

十进制矩阵快速幂

和普通的十进制快速幂实际上也是一样的（已经通过倍增优化）：

mat qpow(mat A,string T)
{
    mat ret=mat(A.n,1),t[20];
    t[1]=A;for(int i=2;i<=9;i++)t[i]=t[i-1]*A;//预处理出A^2到A^9，避免时间复杂度爆炸
    int l=T.size()-1;
    for(int i=0;i<=l;i++)
    {
        if(i)//ret^10，这里通过倍增优化。
        {
            mat x=ret*ret;//x=ret^2
            mat y=x*x;//y=ret^4
            mat z=y*y;//z=ret^8
            ret=z*x;//ret'=(ret^8)*(ret^2)=z*x;
        }
        int now=T[i]-'0';
        if(now)ret=ret*t[now];//注意特判now!=0
    }
    return ret;
}

应用

矩阵加速递推

P1962 斐波那契数列

总结/题解

P1397 [NOI2013] 矩阵游戏
总结/题解

P3758 [TJOI2017]可乐

感觉矩阵这块，知识点很少，但是题做起来却没有做数论那么顺手。其实是我太菜了

所以主要的总结都放在题目总结里面了。知识点总结相对较少。

To be continued……