【线性代数】线性代数基础题

## 1 高斯消元法 线性代数中比较基础的一块。用来解方程。 **SDOI2006 线性方程组** 模板题。建议用这道题作为模板题，而不是洛谷的模板。原因显而易见。 **【模板】矩阵求逆** 矩阵求逆模板题。矩阵求逆也是高斯消元的经典运用。 ### DP 我记得有一道最裸的高斯消元+DP的CF题，但是那题要用带状矩阵的特殊性质（详见froggy的Band Matrix的洛谷日报），所以就不放进来了。 **[USACO10HOL]Driving Out the Piggies G** 期望DP+高斯消元比较板的题了。 **[HNOI2011]XOR和路径** 由于期望的线性性，拆位不妨是一个很好的选择。 ### 异或方程 高斯消元也可以用来解异或方程。具体方法就是消元的时候不需要做减法，异或一下即可（所以其实更简单）。一般需要 bitset 优化。 **[SDOI2010]外星千足虫** 板子题。关于这题额外求得内容，我们可以采取贪心。 **[USACO09NOV]Lights G** 考虑清楚自由元的处理就很简单了。 **[CQOI2014]和谐矩阵** 看似构造，其实就是一道解方程题。 ## 2 行列式 **【模板】行列式求值** 这道模板是真心良心，模数不是质数，所以强烈建议背此题模板而非别的奇奇怪怪的模板。 ### Matrix-Tree **【模板】矩阵树定理** 板子题，没啥好说的。 **[CQOI2018]社交网络** 同样是板子题 **[SDOI2014]重建** 需要先推一小步式子。 **[SHOI2016]黑暗前的幻想乡** 和另一个计数问题常见技巧合起来考，不得不说挺有意思。 **[JSOI2008]最小生成树计数** 尝试去模拟 Kruskal，并解和最小生成树的性质，用乘法原理去解题。 **【模板】BEST 定理** BEST 定理是矩阵树定理的一个衍生的定理。除了比较有意思之外没啥作用了。 ## 3 线性基 **[JLOI2015]装备购买** 其实我觉得应该在异或线性基前先学习一下正常的向量的线性基。这道题就是一个板子。 **【模板】线性基** 异或线性基的模板。 **[BJWC2011]元素** 和上上题除了一个数向量一个是异或之外没啥区别。 **[WC2011]最大XOR和路径** 还结合了图论来考。路径=链 xor 环。