矩阵乘法和高斯消元

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

矩阵乘法 - matrix

概述

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

例题

[UVa 10870] Recurrences

[Description]
有$f(n)=a1×f(n-1)+a2×f(n-2)…ad×f(n-d)$,给定d,a1~ad,f(1)~f(d),求f(n),答案对m取模。
[Hint]
$n<2^{31},d<16,m<46340$

[Solution]
有一种叫“相伴矩阵”的东西可以用来计算这种线性递推关系:
$$
A=
\begin{bmatrix}
0 & 1 & 0 &. & 0 \\
. & . & 1 & .& .\\
. & . & .& 1 & 0\\
0 & . & . & 0 & 1\\
a1 & a2 & - & - & an\\
\end{bmatrix}
$$
另外,包含答案的矩阵Fn为
$$
Fn=
\begin{bmatrix}
f(n-d) \
| \
| \
| \
f(n-1) \
f(n)\
\end{bmatrix}
$$
递推式为Fn=A×Fn-1,也就是Fn=FdAn-d用快速幂求解即可。

[LA 3704] Cellular Automaton

[Description]
n个数组成一个环,给定距离d,每次操作将每个数变为距离这个数不超过d的数操作之前的值之和,问k此操作后环上值的情况,答案对m取余。
[Hint]
$n≤500,k<10^7$
[Solution]
这次“基矩阵”(随便取的一个名字)叫做循环矩阵。
$$
A=
\begin{bmatrix}
1 & 1 & 0 &.& 1 \\
1 & 1 & 1 & 0& .\\
0 & 1 & 1& 1 & 0\\
. & 0 & 1 & 1 & 1\\
1 & . & 0 & 1 & 1 \\
\end{bmatrix}
$$
另外有个优化,我们发现,循环矩阵的第i行可由第i-1行“右移”得来,这样我们可以只计算第一行来推出整个矩阵,时间复杂度缩减到原来的1/n.

高斯消元 - guess elimination

概述

高斯消元法最直接的应用,就是用来解n元n次方程。
以如下方程为例来模拟一下高斯消元的操作:
$$
\begin{cases}
2x+y-z=8 & (1)\\
-3x-y+2z=-11 & (2)\\
-2x+y+2z=-3 & (3)\\
\end{cases}
$$
现在将(1)式乘上相应的系数,用它加减(2)(3)来消去(2)(3)中间的x:
$$
\begin{cases}
2x+y-z=8 & (4)\\
\frac{1}{2}y+\frac{1}{2}z=1 & (5):(1)×\frac{3}{2}+(2)\\
2y+z=5 & (6):(1)×1+(3)\\
\end{cases}
$$
现在将(2)式乘上相应的系数,用它加减(3)来消去(3)中间的y:
$$
\begin{cases}
2x+y-z=8 & (7)\\
\frac{1}{2}y+\frac{1}{2}z=1 & (8)\\
z=-1 & (9):(5)×4-(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_{y|y为x的前驱}sum(y)/d(y)$,其中d(y)为结点y的出度,这个应该很好理解。
那我们是不是就可以直接列方程再高斯消元求解了呢?并不行。
因为方程组不一定有解啊…所以我们先要去除无解(期望值为0)和解出来为无穷的结点,它们分别对应结点1无法到达的点和无法到达结束结点的点,用floyd传递闭包预处理就可以辣。
其实这一步据说可以用高斯-约当直接处理,以后再说吧er…

[UVa 11542] Square

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