速通矩阵

引入¶

矩阵来自于线性方程组，体现了一种对数据「打包处理」的思想。

\[ \begin{equation} \left\{ \begin{array}{c} 7x_1+8x_2+9x_3=13 \\ 4x_1+5x_2+6x_3=12 \\ x_1+2x_2+3x_3=11 \end{array} \right. \end{equation} \]

将上述系数抽出来，写成矩阵（一般用圆括号或方括号表示）乘法的形式：

\[ \begin{equation} \left( \begin{array}{ccc} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3 \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} 13 \\ 12 \\ 11 \end{array} \right) \end{equation} \]

简记为：

\[ Ax=b \]

即未知数列向量 \(x\)，左乘一个矩阵 \(A\)，得到列向量 \(b\)。

列向量：只有一列的矩阵，其余全是0。一般需要左乘矩阵，如上。
行向量：只有一行的矩阵，其余全是0。一般需要右乘矩阵，如下，笔者常用。

Tip

\[ \begin{bmatrix} x_1 & x_2 & x_3 \end{bmatrix} \begin{bmatrix} 7 & 4 & 1 \\ 8 & 5 & 2 \\ 9 & 6 & 3 \end{bmatrix} = \begin{bmatrix} 13 & 12 & 11 \end{bmatrix} \]

我们常把向量存成矩阵，这里的原理就是矩阵的乘法；列向量左乘矩阵仍是列向量，行向量右乘矩阵仍是行向量。

运算性质¶

矩阵的线性运算¶

矩阵的线性运算分为加减法与数乘，它们均为逐个元素进行。只有同型矩阵之间可以对应相加减。

矩阵的转置¶

矩阵的转置，就是在矩阵的右上角写上转置「T」记号，表示将矩阵的行与列互换（沿着斜右下线对称，即主对角线对称）。对称矩阵转置前后保持不变。

在上文中，站在行向量和列向量角度分别推出的矩阵成转置关系。

矩阵乘法¶

矩阵乘法是矩阵与向量乘的拓展。矩阵乘法即：左边矩阵抽出一行，右边矩阵抽出一列，两两对应元素相乘，最后相加（两个向量内积）->得到结果矩阵的对应元素，口诀 「左行右列」。

\[ C_{i,j} = \sum_{k=1}^MA_{i,k}B_{k,j} \]

也就是，抽出左边第 \(i\) 行，右边第 \(j\) 列，\(k\) 遍历该行/列，两两相乘求和：

for(int k=0; k<m; k++) // 放这里速度更快
    for(int i=0; i<m; i++)
        for(int j=0; j<m; j++)
            c[i][j]+=a[i][k]*b[k][j]; // 取模

这里我们注意到，只有 \(A\) 矩阵的列数等于 \(B\) 矩阵的行数（要不然抽出来的两向量阶数不同，没法求内积）矩阵乘法才有定义。并且，矩阵乘法没有交换律，只有结合率和分配率。

使用 unsigned long long 并循环展开减少取模次数，可以获得更小的常数：

for(int k=0; k<m; k+=4)
    for(int i=0; i<m; i++)
        for(int j=0; j<m; j++){
            int kk=k;
            c[i][j]+=a[i][kk]*b[kk][j],kk++;
            c[i][j]+=a[i][kk]*b[kk][j],kk++;
            c[i][j]+=a[i][kk]*b[kk][j],kk++;
            c[i][j]+=a[i][kk]*b[kk][j],kk++;
            c[i][j]%=mod;
        }
// kk超过上界不要紧，全是0不会有任何贡献

其他性质¶

虽然没有交换律，但有：\((A\cdot B)^{T}=B^{T}\cdot A^{T}\)
可交换的矩阵有且只有主对角线为全 \(a\) 的：

\[ \begin{bmatrix} a & 0 & 0 & 0 \\ 0 & a & 0 & 0 \\ 0 & 0 & a & 0 \\ 0 & 0 & 0 & a \end{bmatrix} \]

应用¶

加速线性变换¶

利用结合律，同阶矩阵连乘可以利用快速幂来优化。同时，线性递推式可以构造成矩阵乘法的形式，用矩阵快速幂来求线性递推数列的某一项，递推一项就乘一次转移矩阵，算到第 \(n\) 项的复杂度为 \(O(m^3 \log n)\)，\(m\) 为矩阵阶数。

斐波那契

递推式 \(f_i=f_{i-1}+f_{i-2}\)，求出数列第 \(n\) 项。（\(n \le 1e18\)）

问题的关键在于求出转移矩阵。我们从头开始：

转移需要几个已知量（几个线性无关的量）推出新值，向量和矩阵就为几阶。

用行向量 \(\begin{bmatrix}f_{i-2} & f_{i-1}\end{bmatrix}\) 表示转移前状态；
用行向量 \(\begin{bmatrix}f_{i-1} & f_{i}\end{bmatrix}\) 表示转移后状态。

设矩阵则有等式： \(\begin{bmatrix}f_{i-2} & f_{i-1}\end{bmatrix} \cdot \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix}f_{i-1} & f_{i}\end{bmatrix}\)，展开得方程：

\[ \begin{equation} \left\{ \begin{array}{c} af_{i-2}+cf_{i-1}=f_{i-1} \\ bf_{i-2}+df_{i-1}=f_{i} \end{array} \right. \end{equation} \]

待定系数、代入递推式得：\(\begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\)

初始状态向量为 \(\begin{bmatrix}f_1 & f_2\end{bmatrix}=\begin{bmatrix}1 & 1\end{bmatrix}\) ，乘一次后得到 \(\begin{bmatrix}f_2 & f_3\end{bmatrix}=\begin{bmatrix}1 & 2\end{bmatrix}\) 。求 \(f_n\) 即乘 \(n-2\) 次后，取行向量第二个元素，即矩阵的第一行第二列。

待定系数法固然能行，但是不一定好用。仔细观察方程组，等号的整个右侧组成了下一个向量，而每一行左侧都是前一个向量的每一项乘一个系数。用 \(a[i][j]=k\) 表示矩阵的第 \(i\) 行第 \(j\) 列是 \(k\)，我们可以理解成前一个向量的第 \(i\) 个元素乘以 \(k\) 后给下一个向量的第 \(j\) 个元素做贡献。这样更符合递推式的思想。

四校联考-图形变换

对一个由n个点组成的图形连续作平移、缩放、旋转变换。相关操作定义如下：

Trans(dx,dy) 表示平移图形，即把图形上所有的点的横纵坐标分别加上dx和dy；
Scale(sx,sy) 表示缩放图形，即把图形上所有点的横纵坐标分别乘以sx和sy；
Rotate(θ,x0,y0) 表示旋转图形，即把图形上所有点的坐标绕(x0,y0)顺时针旋转θ角度。

由于某些操作会重复运行多次，翔翔还定义了循环指令：Loop(m) … End
表示把Loop和对应End之间的操作循环执行m次，循环可以嵌套。

如果不加平移，且只绕原点旋转，不难使用二阶矩阵表示出这些变换（线性变换基本的几何意义）。

如果加上平移，向量 \(\begin{bmatrix} x & y \end{bmatrix}\) 用二阶矩阵不足以变换成 \(\begin{bmatrix} x+n & y+m \end{bmatrix}\)。因为多出来一个常数项，即 \(n,m\)。共有三种线性无关的量，故增加一维常数来维护平移：

\[ \begin{bmatrix} x & y & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ n & m & 1 \end{bmatrix} = \begin{bmatrix} x+n & y+m & 1 \end{bmatrix} \]

一般地，递推矩阵中是不能有变量 \(x,y\) 出现的。

把旋转视作 平移到原点->旋转->平移回去，旋转公式可以用和角公式或者复数相乘来推得。于是这道题就做完了。

习题¶

P3176 数字串拆分

P3702 SDOI2017 序列计数

AGC031D A Sequence of Permutations （这个不是矩阵，但是思想相似）