浅谈归约矩乘

（由于我比较菜，所以如果有什么锅或者有什么不对的地方欢迎指出） 应该是打作"归约"而不是"规约"，感谢评论区大佬指正。 如果您有过和lxl谈笑风生的经历，可能会听说过一个叫作归约矩乘的东西，还大概知道它是用来证明一个问题最优时间复杂度不低于某个值的。那么，这个是什么？ 前置知识： [矩阵乘法](https://www.luogu.com.cn/blog/shehuizhuyihao/post-zhen-sheng-fa#) 可能还要一些分块的思想。 ------- 首先先其中一个方向的 其实归约矩乘，就是对于一个问题，如果我们能够证明它不弱于求 两个$m*m$矩阵相乘这样一个问题，那么解决它的时间复杂度也是不低于解决$m*m$矩阵乘法这样一个问题的。 $n*n$的矩阵乘法，目前是没$O(n^2 polylog)$（$polylog$这里表示任意$log^kn$，$k$是一个常数）做法的。 然后对于一种特殊的矩阵，$0/1$矩阵（矩阵里的数只有$0或1$）的乘法，在忽略polygon因子的情况下，最优复杂度和普通的矩阵乘法的时间复杂度是相同的（因为普通矩乘按位拆就是0/1矩阵）。事实上归约矩乘一般都归约成$0/1$矩阵的。 当然，现在也没有证明矩阵乘法没有$n^2*polylogn$的作法。 说了半天还是没办法证明时间复杂度下界，那么这玩意有啥用吗？在做题或者出题时还是比较有用的，毕竟对矩阵乘法已经被学术大佬们研究了很多却也没有$n^2polylog$做法，我们在自己做题时也不至于想出矩阵乘法的$polylog$做法。就像如果你发现一个题是NPC问题，你总不至于去想多项式时间复杂度的算法吧。 于是，对于上述问题，我们就不应当去思考有没有$m^2polylogm$做法。然后事实上，由于那些优于$O(n^3)$的矩乘大多都具有很大的常数，所以在OI上一般找到$O(m^3)$的做法就够了，至于一些时间复杂度更优的做法，就是学术研究的事情了。 ---- (下面默认$n,q$同级) 上面讲的可能有点抽象，那么下面来点例子： ## 问题1： [SP10707 COT2 - Count on a tree II](https://www.luogu.com.cn/problem/SP10707) 题意：给你一棵树，每个节点有一个颜色，若干次询问求树上两个节点路径上的节点的颜色种类数。 我们假定这个题有一个做法,那么对于两个$\sqrt {n/2}*\sqrt{n/2}$的0/1矩阵A,B，$C =A*B$我们考虑构造下面一种情况： 一棵树，从root挂下来$2*\sqrt {n/2}$条链，分为前半部分和后半部分，每部分$\sqrt {n/2}$条。 如果$A_{i,k} = 1$那么就在前半部分的第$i$条链上挂一个颜色为$k$的节点，而$B_{k,j}=1$在后半部分第$j$条链上挂一个颜色为$k$的节点。 $root$的话就随便搞一个大于$\sqrt {n/2}$的颜色。 然后对于$C_{i,j}$，它相当于是$\sum_{k=1}^n[A_{i,k}=1][B_{k,j}=1]$,也就是有多少种颜色$k$,使得在前半部分的第$i$条链中出现且在后半部分的第$j$条链中出现，那么就是 ： 前半部分的第$i$条链节点数 + 后半部分的第$j$条链节点数 + 1 - 两条链链底之间的路径的颜色数。 那么询问就构造 任意的一个前半部分的链链底 到 任意的一个后半部分的链链底 的颜色数就行了（询问数是$O(n)$个）。 也就是说，假如有一种算法,它可以解决这个问题，那么就可以用它来解决$\sqrt {n/2} * \sqrt {n/2}$的矩阵乘法问题，因此这个算法的时间复杂度也一定是不低于$\sqrt {n/2} * \sqrt {n/2}$的矩阵乘法的最优复杂度的。 ## 问题二：小Z的袜子 [problem](https://www.luogu.com.cn/problem/P1494) 题意（略有修改）： 一个序列$a$，若干次询问$l,r$求有多少个点对$(i,j)$使得$l \leq i < j\leq r$，$a_i = a_j$。 建议读者先自行思考以下如何归约。 ---- 做法（仅简述思路）： 考虑对序列成分成$O(\sqrt n)$个块，块分为前半部分的块和后半部分的块。 0/1矩阵$A,B,C$,$C = A*B$ $A_{i,k} = 1$时在前半部分的第$i$个块放入数$k$。 $B_{k,j} = 1$时在后半部分的第$j$个块放入数$k$。 那么$C_{i,j}$就是前半部分第$i$个块对后半部分的第$j$个块的贡献。 定义$Q(i,j)$表示询问前半部分第$i$个块到后半部分第$j$个块的答案。 那么考虑容斥 $C(i,j) = Q(i,j) - Q(i,j-1) -Q(i+1,j) +Q(i+1,j-1)$ 那么即可证明这个问题也是不弱于$O(\sqrt n)*O(\sqrt n)$的矩阵乘法的。 ## 三、区间逆序对 [problem](https://www.luogu.com.cn/problem/P5047) 然后你会发现如果把序列反转一下就那么就可以证明区间逆序对不弱于小Z的袜子。 ## 四、区间加，区间$\le k$的数的个数 现在有修改操作了。 考虑对于序列分成$O(\sqrt n)$块。 0/1矩阵$A,B,C,C=A*B$ $B_{k,j}$表示在第$k$个块放一个数$j$。 然后$A_{i,k}$我们考虑用操作维护。 考虑对于$A$按行的操作。 第$i$行，如果$A_{i,k}=1$那么使第$k$个块就的数相比**最初**的时候$+n$,否则第$i$个块的数应当和最初时相同。(可以知道修改操作总共最多$O(n)$次） 完成了一行的操作后，我们就可以放上询问。 $C_{i,j}$那么就相当于是此时序列里$n+j$的个数（$A_{i,k}=1$要求第$k$个块必须处于$+n$状态，$B_{k,j}=1$要求第$k$个块存在数$j$,这样一个块中才有$n+j$。） 那么我们就询问全局的$\le n+j$数个数 减去 全局 $\le n+j-1$的数个数就行了。 询问也可以知道总共最多$O(n)$个。 于是这个问题也是不弱于$O(\sqrt n)*O(\sqrt n)$的矩阵乘法的。 ---- 现在来说说另一个方向的归约 你们是不是很好奇为什么会有诸如$n^{1.41}$这样的奇妙时间复杂度的做法 其实，这也要用到矩阵乘法，通过一些优于$n^3$的矩阵乘法来优化做法。 还是来点例子吧 还是那个题：(时间复杂度分析忽略polylog因子) 一个序列$a$，若干次询问$l,r$求有多少个点对$(i,j)$使得$l \leq i < j\leq r$，$a_i = a_j$。 考虑根号分治，将出现次数排名最多的 $S$种数 和其他的数分别考虑。 其他的数出现次数最多$n/S$次，所以我们可以对于这类数，转换成二维数点，时间复杂度$O(n^2logn/S)$或者实现的精细点可以$O(\frac{n^2}{S})$。 然后对于排名前$S$的数，考虑分块，分成$S$块。 散块部分直接暴力$O(\frac{n^2}{S})$ 整块部分，我们只要预处理出任意两个块的贡献即可，之后就搞个二维前缀和就行了。 我们将这$S$个数重标号$1 \sim S$ 定义$A_{i,k}$表示第$i$个块 新标号中的$k$出现次数 $B_{k,j}$表示第$j$个块 新标号中的$k$出现次数 矩阵$C = A*B$ 那么$C_{i,j} = \sum_{i=1}^SA_{i,k}*B_{k,j}$，就是块$i,j$间的贡献。 假设我们现在矩阵乘法能做到$O(n^t)$ 那么我们这个题的时间复杂度就是$O(S^t +\frac{n^2}{S})$,利用高中数学知识就可以算出最优是$O(n^{\frac{2t}{t+1}})$ 可以看出，当$t < 3$的时候就就优于$O(n\sqrt n)$了。 当$t$取目前最快的$2.37$,该题的时间复杂度就可以做到传说中的$O(n^{1.41})$ 鸣谢： lxl等Ynoi群的神仙们给的指点。