算法笔记
线性代数
线代题不多,但是都很有些难度.当然OI中的线性代数存在很大程度上的"只取所需"的情况.高斯消元,线性(异或)基加上矩阵优化DP,基本上就是最多的一个运用了.
高斯消元
道理就是初中数学,解多元一次方程组.其实这种用方程组来理解线代是个挺直观的方法.比如向量张成,线形独立.为甚消元后无解/无数解的矩阵列空间不满秩呢?其实就是把每个向量所带的倍数视作未知数,然后解方程组.如果发现解不了或者无数解,就说明这组向量不能唯一确定表示所在空间的所有向量,就不满秩.
例题:矩阵求逆
高斯消元经典应用.就简单直白地用初中思维想.$ A \times A^{-1} =I$ ,相当于 \(A^{-1}\) 是 \(A\) 代表的方程组在常数项为 \(I\) 的每一列时,每一组解作为一列的一个复合.
这样来看,直接用高斯消元求一组解就天经地义了.
用一点"代数"想象力
高斯消元实现细节比较多
-
回代或消成对角
-
判断无解/无数解
-
精度问题,尽量用精度高的double和long double.如果是取模要算逆元.
不保证模数为质数也可做,因为只涉及到一个行之间互相消用到除法运算,采用辗转相除即可.
线形基
就是能够表示空间内所有向量的基底,和二维三维一个道理.
用一个已知向量集建立线性基,这个线性基可以表示所有由已知向量复合而成的向量.
求法就是贪心法,从最高位开始找,如果有带高位的基底就把影响消掉,贪心地放到第一个没有影响的地方.这样的目的是为了避免出现对任意向量高斯消元求解时出现无解/无数解的情况.
异或当然也是线形运算.于是就出现了异或意义的线性基.因为异或的系数只有01,所以可以用来求最大/第k大之类的有用问题.
考虑一个边权为非负整数的无向连通图，节点编号为 \(1\) 到 \(N\)，试求出一条从 \(1\) 号节点到 \(N\) 号节点的路径，使得路径上经过的边的权值的 XOR 和最大。
路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数.
异或线性基的经典应用.考虑两次异或相当于没有操作,每次用一个点出发再回来相当于异或路径上所有环的异或和.因此可以以一条任意路径为基础,考虑所有的环,对环求线性基即可.
优化DP
优化一切递推且满足线性的DP .
与异或的联系
线形代数的常见形式是 加/乘 ,但是也有 加/max 和 异或/异或 等形式也满足线性. 加/max 一般用于优化DP中.而异或一般出现于与异或有关的题.比如经典线性基(其实完全可以当成一种维护元素异或和值的数据结构用).
除此之外,异或有时候可以用在一些逻辑的问题上,用意想不到的方法解决一些问题.
给一个 \(n\) 个点 \(m\) 条边的无向图，你需要将这 \(n\) 个点划分为 \(r\) 个集合，满足条件：
每个点集的导出子图中所有点度数均为偶数。
求出最小的 \(r\) 并输出任意一种划分方案
这道题捋捋思路是有意义的,思维很巧妙.
首先得出需要奇偶性讨论.
如果度数全为偶数,全都归到一个集合就可以了.
如果度数存在奇数,发现没有什么想法了,就从简单情况考虑.假设只有两个集合,设为0,1.
因为每一个点,要保证有偶数个点与自己在同一集合,0/1状态,奇偶性,就联系到了异或问题.
考虑可行性,偶数点需要保证联通的点有偶数个0,偶数个1,显然有充要条件异或和为0.奇数点要保证联通的点有偶数个与自己相同,两种集合的数量一奇一偶不太好研究,转化一下,带上自己并不影响状态本身,但是要做的就是把带自己的集合划分成奇数+奇数,也就是异或和为1.
到这里发现,要求的问题变成了一个 &/xor 的多元一次方程组问题,系数矩阵就是邻接矩阵.就可以愉快地魔改高斯消元解决了:
二进制运算的系数只有 0/1 ,所以消元操作只用到整行"减",也就是一行异或另一行.于是可以用bitset优化,每次直接把一个长度为 \(N\) 的bitset相互异或,降低了瓶颈上的复杂度,可以通过.
行列式
最经典的结论就是LGV和矩阵树,背下来就行了.
求行列式的基本方法是高斯消元成三角矩阵,然后对角线相乘.
这个做法是基于行列式的基本意义的,所以可以拿着行列式性质魔改.
来自某场逆天省选膜你赛:
