矩阵乘法学习摘记

​ ——JZYshuraK 18.4.8

http://www.matrix67.com/blog/archives/276

例题1

​ 为什么一定要将本来只有两维的点设为一个\(1\cdot 3​\)矩阵，原因在于，我们在处理所有操作时，必须使得每一个操作矩阵都是正方形(显然)，然后加法矩阵需要有一维使得和坐标的另一维乘积为0，而且必须点当中有一维为1，才能实现加法操作。然后，所有矩阵必须都是等大的，进而，所有本可以2*2的矩阵被强行扩大到3*3。

例题2

​ 虽然矩阵不是数，但是它可以相乘。快速幂的本质其实是指数的二进制拆分，对于相乘元素只要可以相乘即可。快速幂中所有元素都是相等的，不存在什么交换律结合律什么的。

例题3

​ 其实并不是什么二分，知道了元素个数可以O(1)知道中间元素，如果是就是就把它单独拎出来算掉，然后递归即可。
考试的时候碰见了一道题，范围是\(10^18\).
有两种做法
我的做法是对于任意的n，将需要单独拎出来的下标存在一个数组里，然后预处理出来。直接处理显然会T。我们发现，每一个数a[i+1]和a[i]的关系很简单，无非就是2,2+1,*2-1。除了-1我们都可以直接×2，然后再扯。对于-1的情况，我在开始dp的时候就弄一个Shadow矩阵，是\(T^{a[i]-1}\)。这样的话，我无论下一个数是不是-1的情况，我都让这个Shadow矩阵一直跟着我们dp的指针。这样的话，我们就处理掉了-1的情况，时间复杂度变成了log
题解的做法是在快速幂的时候直接得到答案。做法是这样的：首先，为什么快速幂能恰好将n算完整？因为我们相当于将n二进制拆分，之后对于是1的情况单独处理。而这里，我们在快速幂的时候顺便将sum矩阵跟着求出来即可。-----------------2018.7.7

例题4

​ 其实这道题可以用Matrix67的方法，最本质的原因是这是置换。这意味着什么？意味着我的操作矩阵和原序列是毫无关系的qwq，所以可以矩阵乘法加快速幂，即可。

例题5

​ 细菌和上一题类似，操作矩阵和原来培养皿里面呆着多少小东西并没有多大关系。所以我把原序列扔进数组，然后撇到一边。可以在线处理(离线MLE)矩阵，然后快速幂即可。最后将操作答案矩阵和原序列相乘，即可。

例题6

​ 求Fibonacci第n项，n是\(2^{31}-1\) (这反倒是我矩乘第一题)。这种问题可以得以解决关键在于这个递推法则是固定的，而且和当前元素下标无关(如果和下标有关，那么操作矩阵中必须存在变量，这样就不符合快速幂的本质(交换律))。

例题7

​ 显然，通过这道题，我们可以大致的猜想到：任意的\(a_n=\sum\limits_{i=n-sum+1}^{n-1} H_i\cdot a_i\) ,(H是固定系数，sum是固定递推项数)，都可以通过矩阵快速幂解决。

例题8

​ JLOI2018 D2 T1裸题

​ 就是说构造邻接矩阵时候，我们矩阵中i行j列的元素，在第k个答案矩阵上，表示从i到j花费k步的方案数。然后。然后，将当前答案矩阵乘上原来的邻接矩阵，如果能对当前点有更新，当且仅当两点之间连边。

​ 即：\(a_{i,j,k}=\sum\limits_{mid=1}^{n}a_{i,mid,k-1}\cdot c_{mid,j}\) 其中，\(a_{i,j,k}\) 表示从i到j用k步的方案数，mid可以看做枚举到达j的上一个点，\(c_{i,j}\) 表示两点是否连通。这恰好枚举了所有情况，其中\(c_{i,i}\) 为0。

​ 之后，求邻接矩阵的k次快速幂，询问的话，输出答案即可。

例题9

​ 额外链接http://blog.sina.com.cn/s/blog_77dc9e08010176nf.html

​ 和例题8类似，只不过这题的邻接矩阵的建立需要花一份儿功夫，建立了所谓的邻接矩阵之后，快速幂即可。

例题10

​ 特别地，我们对于两个病毒片段的转移构造邻接矩阵(详情说的很清楚)。然后同理，矩乘快速幂即可。