前言：总结了一下期中考试后OI和学习上的一些收获，以及需要接下来加强的地方
———————————————————————————————————————————————————————————————————————————————————————————————————————————
我们该航向怎样的未来 无数交织自传 相遇在汪洋中 当你抬头看 何时那万种渐层的斑斓 会默默绽放在 黑夜终端——五月天《少年他的奇幻漂流》
2024.05.28-2024.05.30 矩阵快速幂
1.基础知识：矩阵乘法
其中c[i][j]是A的第i行和B的第j列对应乘积的和
显然，矩阵乘法的复杂度是O(n^3)
矩阵快速幂
就是算A^n，方法很简单，把快速幂中的乘法改成矩阵的乘法就行了
T1序列的第k个数
等差数列用性质去套就行，用乘法，然后等比数列就是快速幂，然后因为学的是矩阵快速幂，所以用矩阵优化
T2斐波那契数列
板子题，自己找题解吧qwq
T3行为方案
应该可以构建按照题意建图，然后构造一个邻接矩阵，矩阵快速幂优化
我们设它的ac次方表示表示ac步后的方案数
那么在原地停留和自爆怎么处理？
在原地停留很简单，我们只要认为每个点都有一个从自己到自己的自环即可。
那自爆呢？
我们可以将自爆这个状态也看成一个城市，就设它为编号0。我们在邻接矩阵上从每个点都向0连一条边，0除了自己外不连其他出边。
这样就满足了任何一个点随时可以自爆，且无法恢复到其他状态。
最后统计答案就行
T4矩阵求和
构造一个包含A的转移矩阵AC，然后记得AC^(k+1)的右上角减去n*n
然而不会使用数学编译器qwq
T5最短路径
是DP，设f[i][j][k]表示从i走到j的k条路的最短路径长度之和，所以方程如下：
f[i][j][k]=min(f[i][t][k-1]+f[t][j][1])
因为在转移是k只与k-1有关，所以可以简化三维f[i][j]=min(f[i][t]+f[t][j])
这个就是矩阵快速幂，所以走n条路就等于把方程看为矩阵进行n次的矩阵乘幂，最后就是f[s][e]
然后，需要离散化！！这是伟大的AC_love告诉我的
我不知道怎么离散化
标签：总结,AC,期中考试,矩阵,自爆,快速,乘法 From： https://www.cnblogs.com/MerlinForLee/p/18223073