有向图和矩阵乘法

给定一个有向图，问从 $A$ 点恰好走 $k$ 步（允许重复经过边）到达 $B$ 点的方案数 $\mod p$ 的值。

类似问题，问从 $A$ 点走 $k$ 步是否能到 $B$ 点。

把有向图转化为矩阵，若 $i \rightarrow j$ 有一条路径，则 $A(i,j) = 1$ 。

令 $C=AA$ ，那么 $C(i,j) = \sum_k A(i,k)A(k,j)$ ，相当于从点 $i$ 到点 $j$ 恰好经过 $2$ 条边的路径数（枚举 $k$ 为中转点）。

推理到 $C = A^k$ ，$C(i,j)$ 就表示从点 $i$ 到点 $j$ 恰好经过 $k$ 条边的路径数。直接用矩阵快速幂即可。

类似问题可以直接把矩阵乘法时的运算定义成与操作即可，即$C(i,j) = \sum_k A(i,k)\&A(k,j)$

# 斐波那契数列和矩阵乘法

就是利用矩阵乘法优化递推式。根据递推式可以构造出矩阵。 $f(n) = \left \{\begin{array}{ll} {1} & {n=1,2} \\ {f(n-1)+f(n-2)} & {n\ge 3} \end{array} \right.$ 可以构造出矩阵 $A= \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix}$ 原始矩阵是 $A_0 =\begin{bmatrix} f(1)&f(2) \\ 0&0 \end{bmatrix}$

\[f(n) = [A_0A^{n-2}]_{(0,0)}\]

其他的递推式也可以通过这种方式构造出来。

几何变换和矩阵乘法

在计算几何中有时会用到旋转、平移等操作，这时也会用到矩阵乘法。

以下是几种常见的变换方式，当然也有不同的表示形式，不过原理是相同的。

递归和矩阵乘法

求 $A + A^2 + A^3 + … + A^k$ 的结果（两个矩阵相加就是对应位置分别相加）。输出的数据 $\mod m$。$k<=10^9$。

举个例子 $\begin{align*} &A+A^2+A^3+A^4+A^5+A^6 \\ = &(A+A^2+A^3)+A^3(A+A^2+A^3) \end{align*}$ $ A^i$ 可以快速求出，就可以递归求解了。

当 $k$ 是奇数时，递归 $k-1$ 项，最后一个单独算即可。

骨牌铺排和矩阵乘法

用 $1$ x $2$ 的多米诺骨牌填满 $M$ x $N$ 的矩形有多少种方案，$M<=5，N<2^{31}$，输出答案 $\mod p$ 的结果.

以 $M=3$ 为例。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前 $n-2$ 列已经填满了，第 $n-1$ 列参差不齐。现在我们要做的事情是把第 $n-1$ 列也填满，将状态转移到第 $n$ 列上去。由于第$n-1$ 列的状态不一样（有 $8$ 种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前 $8$ 种不同的状态放在左边，转移后 $8$ 种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第 $n-1$ 列竖着放一个多米诺骨牌（例如左边第 $2$ 种状态不能转移到右边第 $4$ 种状态），否则这将与另一种转移前的状态重复。把这 $8$ 种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态 $111$ 出发，恰好经过 $n$ 步回到这个状态有多少种方案。

比如，$n=2$ 时有$3$ 种方案，$111\rightarrow011\rightarrow111、111\rightarrow110\rightarrow111 $ 和 $111\rightarrow000\rightarrow111$，这与用多米诺骨牌覆盖 3x2 矩形的方案一一对应。

参考

http://www.matrix67.com/blog/archives/276

https://blog.csdn.net/qq_31557939/article/details/78143967