归约矩乘。——败犬堂而皇之成队 最后更新于 2025-05-01 20:25:16

[b 站讲解视频](https://www.bilibili.com/video/BV1ag411C7e3?spm_id_from=333.337.search-card.all.click&vd_source=df97503f220a80de43a0f184365dc9e9) [dwt's kth 问题收纳](https://www.luogu.com.cn/blog/dowhiletrue/some-reduction) # 前言 副标题选自《欢迎来到实力至上主义教室》第二季 op 《Dance In The Game》歌词。 归约矩乘。 首先请 tly 镇楼： [](https://imgtu.com/i/jjNmLQ) 其实除非Ynoi，个人感觉现OI界倒确实没有什么ds题一走上来就让人感觉极其非常见，绝大部分题经过一定的转化都可以变成一些基础形式，所以背背模型也是比较有效的举措。 记得以前和@[jerry3128](https://www.luogu.com.cn/user/27338#main)探讨过如何知道你代码里 LCT 的一些操作有没有写错（时间复杂度上），基本都是转化成一些基础形式如 access,splay 等等，你不可能一个个势能分析把这个东西整出来，太浪费时间了。 可能引用的不是很恰当，不过前言不是~~都是随便写写吗~~。 有错帮忙评论区指指吧/bx。 # ~~龟~~归约 为了防止大家打成规约，我建议大家可以先都打成龟约，这样你就知道你一定打错了归字。 一篇讲归约讲的很好的[文章](https://zhuanlan.zhihu.com/p/194313998)。 从中我们可以知道，归约是一个动词，把 A 归约到 B 问题上的意思就是，**任意的** A 问题都可以通过一种计算方式转化成 B 问题，而 B 问题是一个在要求范围内已经被解决的问题。 在 OI 领域归约有两种常用方式：一是用来证明问题的解决，例如我们可以将乘法归约到加法，也就是将 $A \times B$ 转化成 $B$ 个 $A$ 相加；二是用来解决一个问题的时间复杂度下界，例如我们可以将区间众数归约到一些问题上面，那么如果我们能解决该问题就一定能解决区间众数问题，而区间众数问题是 $O(n ^ {\frac{3}{2}})$ 的，所以该问题的时间复杂度下界应该至少也是 $O(n ^ {\frac{3}{2}})$。 个人有一个理解：需要注意的是在进行第二类归约时，一定要注意有时候我们需要转化成等价的问题，而问题的转化计算一定要是常数级计算，否则得到的时间复杂度下界也是非严格下界。 所以这也是为什么你背模型是对的，归约矩乘始终是归约，而你如果能构造一个归约法则套到一个模型上，那还不是归约，凭什么不对？ 由于归约矩乘是第二类的归约，对于第一类的归约就得看你平日对于题目的积累了。 # 第一类归约例题 这里只举一道最近做的，因为懒得找了。（也许后面有时间了再加加） [CF1147F](https://www.luogu.com.cn/problem/CF1147F)。 我们需要寻找一种完全匹配，使得对于任意两组匹配 $(a,b),(c,d)$ 满足若 $w_{a,b} > w_{b,c}$ 则 $w_{b,c} < w_{c,d}$。 将稳定婚姻匹配问题的优先级条件根据题意转化成边权条件后我们惊奇地发现，稳定婚姻匹配问题在此题的条件为 $w(b,c) < w(a,b)$ 且 $w(c,b) > w(c,d)$，稳定婚姻匹配问题的条件包含了题目要求的条件，故我们可以将该问题归约到稳定婚姻匹配问题。由于稳定婚姻匹配总是有解的，所以该问题也一定有解。 # 归约矩乘及其例题 通过对归约的充分理解，归约矩乘你都可以才出来是在干什么：把一个 $n \times n$ 矩阵的矩阵乘法归约到待解决的问题上。虽然我们知道矩阵乘法的最优时间复杂度现在已经是 $O(n ^ {2.37})$，但是我们平时使用的时候还是默认为 $O(n ^ 3)$ 计算。 你也可以记住一句话：**将原问题转化为任意的矩阵乘法。** 而不是特殊的矩阵乘法。有时候也需要将原问题特殊构造。 这里根据树剖的[文章](https://www.luogu.com.cn/blog/Ynoi/qian-tan-gui-yue-ju-cheng)有三道例题。 [SP10707](https://www.luogu.com.cn/problem/SP10707) 任意形态树上数链颜色。 我们钦定树上只有 $\sqrt n$ 种颜色，从根延伸 $\sqrt n$ 叉个链，分为前半部分 $\frac{\sqrt n}{2}$ 和后半部分 $\frac{\sqrt n}{2}$ 条链。 记大小为 $\sqrt n \times \sqrt n$ 的矩阵乘法 $A \times B = C$，令 $A_{i,j} = 1/0$ 表示前半部分第 $i$ 条链是/否有第 $j$ 个颜色，$B_{j,i}$ 表示后半部分第 $i$ 条链是/否有第 $j$ 个颜色。 若 $C_{i,j}$ 表示前半部分第 $i$ 条链和后半部分第 $j$ 条链的颜色种类，则 $C_{i,j} = \sum_{k = 1} ^ {\sqrt n} [A_{i,k} ~\text{or}~ B_{k,j}]$。 显然我们将 $A,B$ 矩阵的 $0/1$ 值全部执行 $0$ 变 $1$，$1$ 变 $0$ 操作变成 $A',B'$，由于 $0/1$ 矩阵意义下 $\times$ 等于 $\text {and}$ 操作，所以若将 $C' = A' \times B'$，再将 $C'$ 执行值交换操作即可得到 $C$，显然遍历矩阵的时间复杂度低于矩阵乘法的时间复杂度，这可以被视为一个常数级别的转化。 显然任意的一个 $0/1$ 矩乘也可以被还原变成一个上述的链上查询问题，满足特殊构造原问题可以转化为任意的 $0/1$ 矩乘，归约成立。 [P1494](https://www.luogu.com.cn/problem/P1494) 区间数 $i < j,a_i = a_j$ 的 $(i,j)$ 对数，记**不处理块内对数的答案**为 $Q(l,r)$。 分块，同样假设颜色数量级为 $O(\sqrt n)$。设 $A_{i,k}$ 表示的是第 $i$ 块里面颜色 $k$ 的数量，$B_{k,j}$ 表示的是第 $j$ 块里面颜色 $k$ 的个数。 这里不用前后划分 $A,B$ 矩阵我觉得没有太大关系，都是一个常数的放缩。 令 $C = A \times B$，则 $C_{i,j}$ 表示的是第 $i$ 块和第 $j$ 块互相贡献的答案。 还是容斥，发现 $C_{i,j}$ 可以写成为常数个 $Q(l,r)$ 的形式，构造 $n$ 个询问求出所有的 $Q(l,r)$，则我们可以得出所有的 $C_{i,j}$，我们也就证明了给定数量级询问可以得到矩乘的答案。 而也显然的是，任意矩乘都可以被写成一个上述的问题，所以归约成立。 这里只算块与块之间的贡献是因为块内之间的贡献是可以直接扫一遍的，相对而言较为平凡。 同时我们注意到块与块的贡献与矩阵乘法的归约是双向的，即我们块与块之间产生贡献的问题可以归约到任意的矩阵乘法上面去，而矩阵乘法也可以归约到任意的块与块之间产生贡献的问题上面去，这个问题实际上是等价的。 而像上文的链数颜色问题，矩阵乘法是不能归约到任意的链数颜色上面去，因为树的形态一旦多改改就寄掉了。 [P5047](https://www.luogu.com.cn/problem/P5047) 区间逆序对。这里主要从问题强弱的角度说明。 我们知道一个偏序问题的时间复杂度应该只取决于维度，所以区间正序对和区间逆序对的时间复杂度应该是相等的。 记区间正序对数为 $A(l,r)$，区间逆序对数为 $B(l,r)$，P1494 的区间询问答案为 $C(i,j)$，我们构造一个容斥 $\frac{(r-l+1)(r-l+2)}{2} = A(l,r) + B(l,r) + C(l,r)$。 左式的计算是平凡的，所以我们如果知道了 $A(l,r),B(l,r)$，就可以计算 $C(l,r)$。这说明了区间逆序对不弱于小 Z 的袜子，即是不弱于矩阵乘法的。 我不是很会这道题的双向归约，我个人只会证单向，如果有谁会的话可以补充一下。 # 一些经典的有归约的问题 我直接从 lxl 的 ppt 里面摘的，这里他默认的肯定还是矩乘的时间复杂度最优做法是 $O(n ^ {2.37})$。 [](https://imgtu.com/i/jxtoZQ) [](https://imgtu.com/i/jxt5qg) 除了上文讲的三道例题，我们也浅了解一下其它例题的证明方法。 - **区间出现奇数次的数个数** 这道题首先有一个上树的版本在 cf 上是求是否有数出现奇数次，我们可以给一个颜色赋一种值然后维护区间按位异或即可得到一个 polylog 的期望正确率极高的做法，这是一种特殊情况，我们不考虑。 我们考虑对序列分块，设序列上一共只有 $\sqrt n$ 种颜色，设 $A_{i,j}$ 表示第 $i$ 个块第 $j$ 个颜色的奇偶性，$B_{j,i}$ 表示第 $i$ 个块第 $j$ 个颜色的奇偶性，若 $C_{i,j}$ 表示的是第 $i$ 到第 $j$ 个块区间出现奇数次的数个数，则 $C_{i,j} = \sum_{k = 1} ^ {\sqrt n} A_{i,k} ~\text{xor}~ B_{k,j}$。 写成 $C_{i,j} = \sum_{k = 1} ^ {\sqrt n} [A_{i,k} ~\text{or}~ B_{k,j}] - [A_{i,k} ~\text{and}~ B_{k,j}]$，然后再将 $\text{or}$ 转化成 $\text{and}$ 即可归约成矩阵乘法，套路和例题 $1$ 是一样的。 - **区间最大 $|i - j|$ 满足 $a_i = a_j$** 发现块内贡献还是可以直接扫一遍处理的，视为常数级操作。 将序列分块，设颜色数为 $\sqrt n$ 种，设 $A_{i,j}$ 表示第 $i$ 个块里面颜色 $j$ 最靠左的位置，$B_{j,i}$ 表示第 $i$ 个块里面颜色 $j$ 最靠右的位置，$C_{i,j}$ 为块 $i$ 与块 $j$ 内相互贡献的答案。 则 $C_{i,j} = \max_{k = 1} ^ n (-A_{i,k} + B_{k,j})$ 将询问设成 $n$ 次任意两两块的询问，用 $C_{i,j}$ 可以求出所有的询问，即证明了矩阵乘法可以回答原询问，同时任意的 max-plus 矩阵乘法都可以被转化成特殊构造的原问题，归约成立。 - **区间加，区间 $\leq k$/排名** 这个就是树剖的例题四，排名就直接二分一下就变成 $\leq k$ 了。 - **区间众数** 如果是求出现次数可以同样使用 max-plus 矩阵乘法进行归约。 分块，设有 $\sqrt n$ 种颜色，设 $A_{i,j}$ 表示**前** $i$ 个块内有多少个颜色 $j$，$B_{j,i}$ 表示**前** $i$ 个块内有多少个颜色 $j$，令 $C_{i,j} = \max_{k = 1} ^ {\sqrt n} (-A_{i,k} + B_{k,j})$ 即可令 $C_{i,j}$ 表示第 $i+1$ 个块与第 $j$ 个块相互贡献的答案。用矩阵乘法可以解决原问题。 同时我们也可以证明任意的 max-plus 矩阵乘法可以被转化成原问题，归约成立。 # 感谢 感谢 u 群神仙，thu 学者 ccz，我校集训队学长 tly，朋友 dwt 和 dqstz 在我学习归约矩乘时对我的帮助。 感谢特约审稿人 gxy。