高斯消元这个坑竟然现在才来补…
感觉这两个东西放在一起有一点点强行（雾

矩阵乘法 - matrix

概述

概念什么的不用多说，n×m的矩阵乘m×q的矩阵=n×q的矩阵， $c[i][j]=\sum_{i,j,k}(a[i][k]×b[k][j])$ ，大概就这样…
实现上 $O(n^3)$ 已足够。

例题

[UVa 10870] Recurrences

[Description]
有 $f(n)=a_1×f(n−1)+a_2×f(n−2)…a_d×f(n−d)$ ，给定 $d,a_1~a_d,f(1)~f(d)$ ，求 $f(n)$ ，答案对 $m$ 取模。
[Hint]
$n＜2^{31},d<16,m<46340$
[Solution]
有一种叫“相伴矩阵”的东西可以用来计算这种线性递推关系:

$A= \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ \cdots & \cdots & 1 & \cdots & \cdots \\ \cdots & \cdots & \cdots & 1 & 0 \\ 0 & \cdots & \cdots & 0 & 1 \\ a_1 & a_2 & \cdots & \cdots & a_n \\ \end{bmatrix}$

另外，包含答案的矩阵Fn为

$F_n=[f(n−d) | | | f(n−1) f(n) ]$

递推式为 $F_n=A×F_{n-1}$ ,也就是 $F_n=F_dA^{n-d}$ 用快速幂求解即可。

[LA 3704] Cellular Automaton

[Description]
n个数组成一个环，给定距离d，每次操作将每个数变为距离这个数不超过d的数操作之前的值之和，问k此操作后环上值的情况，答案对m取余。
[Hint]
$n≤500,k<10^7$
[Solution]
这次“基矩阵”（随便取的一个名字）叫做循环矩阵。

$A= \begin{bmatrix} 1 & 1 & 0 & \cdots & 1 \\ 1 & 1 & 1 & 0 & \cdots \\ 0 & 1 & 1 & 1 & 0 \\ \cdots & 0 & 1 & 1 & 1 \\ 1 & \cdots & 0 & 1 & 1 \\ \end{bmatrix}$

另外有个优化，我们发现，循环矩阵的第i行可由第i-1行“右移”得来，这样我们可以只计算第一行来推出整个矩阵，时间复杂度缩减到原来的1/n.

高斯消元 - guess elimination

概述

高斯消元法最直接的应用，就是用来解n元n次方程。
以如下方程为例来模拟一下高斯消元的操作：

$\begin{cases} 2x+y−z=8, & \text{(1)} \\ −3x−y+2z=−11, & \text{(2)} \\ −2x+y+2z=−3 & \text{(3)} \end{cases}$

现在将(1)式乘上相应的系数，用它加减(2)(3)来消去(2)(3)中间的x:

$\begin{cases} 2x+y−z=8, & \text{(4)} \\ \frac{1}{2}y+\frac{1}{2}z=1, & \text{(5):(1)}\times \frac{3}{2}+\text{(2)} \\ 2y+z=5 & \text{(6):(1)+(3)} \end{cases}$

现在将(2)式乘上相应的系数，用它加减(3)来消去(3)中间的y:

$\begin{cases} 2x+y−z=8, & \text{(7)} \\ \frac{1}{2}y+\frac{1}{2}z=1, & \text{(8)} \\ z=-1 & \text{(9):(5)}\times 4-\text{(6)} \end{cases}$

最终得到的方程组中，倒数第i个方程有i个未知数，从最后一个方程开始解，带到前面的式子中，这样就可以解出所有未知数。

优化

因为实数运算的问题，高斯消元法对精度的控制不是很佳，但在一般情况下已经完全够用（若要求更高，请参看高斯-约当消元法和选主元消去法）。
但我们可以尽量优化高斯消元的精度，一是尽量少使用中间变量，二是处理第i行时，可优先把当前第i个未知数系数绝对值大的提前到第i个来处理（方程顺序并不影响结果），这样可提高数值稳定性。

代码参考

用矩阵来实现，准确时间复杂度为 $O(\frac{n^2}{3}+n^2−\frac{3}{n})$ .

例题

[UVa 10828] Back to Kernighan-Richie

[Description]
给定一个n(n≤100)个点的有向图，从结点1开始访问，结点到每个后继结点的概率相同，当结点没有后继时访问结束。问每个点的期望执行次数。
[Solution]
设结点x的期望执行次数为 $sum(x)$ ,有 $sum(x)=\sum_{\text{y|y为x的前驱}}sum(y)/d(y)$ ,其中d(y)为结点y的出度，这个应该很好理解。
那我们是不是就可以直接列方程再高斯消元求解了呢？并不行。
因为方程组不一定有解啊…所以我们先要去除无解（期望值为0）和解出来为无穷的结点，它们分别对应结点1无法到达的点和无法到达结束结点的点，用floyd传递闭包预处理就可以辣。
其实这一步据说可以用高斯-约当直接处理，以后再说吧er…

[UVa 11542] Square

[Description]
给定n(n≤100)个64位整数，问有几种选数方案，使得选出来的数乘积为完全平方数。