矩阵 总结
前言
矩阵是一种较为基础的数学工具，OI里面好像不常考？，反正学完数学一本通里的矩阵，做一些矩阵的应用感觉就应该可以了。行列式也是很有趣的东西，我花时间钻研了一下。下面归纳总结一下我做过的一些矩阵的题型
如果定义这种不会请百度吧 -> 百度矩阵
矩阵乘法
矩阵里面最主要的一种。下面是矩阵乘法的一些题。
- 矩阵快速幂
P3390模板题 基础。
- 矩阵加速递推数列
P1939模板题 加速加法递推直接设状态转移矩阵就好了。
石头游戏 其实想清楚了石头要从一个格子转移到另一个格子，就可联想到用矩阵来表示格子与格子间的的转移。码量有点大。
Codeforces 1182E Product Oriented Recurrence 加速乘法递推数列。这类题首先要把c和f拆开来分别处理。转换一下思维，令 \(f_i=f_1^p*f_2^q*f_3^r\)，这时候我们就可以对 p,q,r 进行矩阵加速数列处理（找出 p,q,r 转移的规律）。同样的方法令第x项的c的次数为\(k_x\)，有 \(k_x=k_{x-1}+k_{x-2}+k_{x-3}+2*x-6\)。总结：乘法递推序列这类题就把递推放到指数上来。Talk is cheap.Show me the code.
Codeforces 1117D Magic Gems 自己写出来一个dp方程，发现这个方程可以用矩阵加速，OK。Talk is cheap.Show me the code.
- 其他矩阵乘法
Codeforces 1252K Addition Robot 把线段树上的点看成矩阵，就可以表示这些运算（突然发现矩阵乘法还可以这样用），线段树维护区间乘。修改就是‘A’，‘B’互换，所以我们每个点保存两个矩阵，比如我们保存一个该区间当前矩阵‘ABBB’，再保存一个可能会翻转成为的矩阵‘BAAA’(字母对应矩阵，点保存矩阵乘积)，修改就交换一下好了。
更多请关注 -> 矩阵刷题题单
总结一下几种题型以及方法：
1.给出加法递推数列，求第n项\((n<=10^{18})\)。做法：根据题目写转移矩阵，可能会有一些小技巧，要自己想。
2.给出乘法递推数列，求第n项。做法：看一下 \(f_i\) 可否写成 \(a^p+b^q+...+c^r\)的形式，考虑 \(p,q,r\) 可以用加法递推（矩阵加速）求得。（好吧，我这做过一个题）
3.给出一个模拟，求n秒后的状态\((n<=10^{9})\) 做法：看一下状态转移能不能用矩阵乘法表示出来，如果能就想办法矩阵加速一下。
4.给出一个dp，求dp[n]，\((n<=10^{9})\) 做法：把dp写出来，看一下能不能用矩阵乘法表示转移，如果能就想办法用矩阵加速一下。
5.给出一些加减乘除，做一些七七八八的东西。(雾 做法：看一下加减乘除符不符合矩阵乘法，如果符合就往矩阵上去想，看一下能不能矩阵乘法套出来(大雾
高斯消元
求n元1次方程组的解，时间复杂度 \(O(n^3)\)，下面给出一些题目。
- 普通消元
高斯消元 一般步骤：对每一列的主元以下的元素消元，使得最后只剩下一个上三角矩阵，对上三角矩阵进行回代，解出方程组。每一次选主元要选最大的这个元素。
高斯-约旦消元 一般步骤：把矩阵消成一个对角矩阵，对角矩阵上有系数，最后输出答案是要消去系数
线性方程组：用高斯约旦消元，最后n个方程形如 \(k_i*x_i=b_i\)，先判无解：如果 \(k_i=0,b_i≠0\) 则无解；再判无数解：如果 \(k_i=0,b_i=0\) 则无数解。注意判 \(==0\) 时最好和 eps 比较，判断 \(fabs(a)<eps\)，避免精度问题。
[HNOI2013]游走 列出dp来，发现dp没有先后顺序，可以用高斯消元搞一下啦。
- 其他特殊消元
[LnOI2019]加特林轮盘赌 列出dp来，发现dp没有先后顺序，可以用高斯消元搞一下啦。 发现数据范围不太对，\(n<=10^4\)。发现可以手动消元，手动消元 \(O(n^2)\)（没有跑满）就好了。Talk is cheap.Show me the code.
总结一下几种题型以及方法
1.给你一个线性方程组，让你判断解，无解，无数解的情况。做法：可以使用高斯约旦消元，无解就是 \(k_i=0,b_i≠0\) ，无数解就是 \(k_i=0,b_i=0\)。
2.给你一个问题，求一些东西，且这个问题可以列出线性方程组来。做法：想办法列出线性方程组，对这个线性方程组求解。
3.给你一个dp题，dp的转移这里发现没有先后顺序。 做法：一般这种题都可以列出n个n元1次方程组，求解即可得到dp值。常见的题有图上的概率dp
4.给你一个dp题，dp的转移没有先后顺序，\(n>1000\) 做法：和上一种一样，只不过可能要考虑一下手动消元
投递美团等公司10个岗位 >
