祝馀宫

算法简介：巡护深林KMP 算法，虽然我们已经在 【算法介绍】字符串算法 | 祝馀宫 中提及，但是现在有了更深的理解，我们这篇文章单独讲 KMP 算法以及其原理。为了凑字数，我们再讲一遍废话。 KMP 算法，全称 $Knuth-Morris-Pratt$ 算法，通过一种特殊的性质匹配两个字符串，从而达到减少匹配次数的算法。 算法演示：漫行山薮变量定义：夏堇芳菲我们对于接下来的一些内容做出如下定义： 名称 定义 子串 不用多说了罢，在字符串中截取任意一段连续的内容，被称为子串下文用 $s[l\dots r]$ 表示字符串 $s$ 的从 $l$ 到 $r$ 的这部分子串。 下文所有关于字符串的计算都是以 1 为开始的下标* 子序列 不要求连续，但是在原字符串中内容顺序相同的字符串。 前缀子串 一个字符串的前缀组成的子串，表示为 $pre(s,i)=s[1\dots i]$ ，即 $s$ 字符串长度为 $i$ 的前缀 后缀子串 一个字符串的后缀组成的子串，表示为 $suf(s, i) = s[n-i+1\dots n]$ ，即 $s$ 字符串长度为 $i$ 的后缀 ...

算法简介：正绢六通首先，说到矩阵乘法。字面意思的来讲，就是矩阵与矩阵之间的乘法，他们之间是否满足正常数字之间的乘法规则，也就是交换律与结合律呢？这部分的内容都将在下面被解释。 算法演示：落染五色矩阵加法：缀锦四分这个比较简单。首先我们了解一下矩阵的定义，对于一个 $n$ 行 $m$ 列的矩阵，我们有如下的表示方式： \left[\begin{matrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m} \end{matrix}\right]这样的矩阵，就是我们接下来的基础。首先讲到乘法，肯定会有人想到加法。但是实际上……矩阵的加法和乘法几乎一点关系都没有……但是提到了我们也顺便讲一下。 矩阵的运算不同于数字，两个矩阵之间是否可以进行运算，对于矩阵的行和列有着严格的规定。比如说加法，所对应的两个矩阵行和列必须一模一样，因为矩阵加 ...

算法简介：重帘留香树上莫队，就是字面意思上的树上的莫队，但实际上，一般来讲的树上莫队指的都是用欧拉序把一棵树压成数组，然后对其进行普通莫队的操作。 算法演示：天青现虹算法推导：织诗成锦那么首先我们可以随便画一棵树 然后我们首先手动算一算他的欧拉序。应该是 $[1,2,4,5,5,6,6,7,7,4,2,3,3,1]$ 。 那么我们考虑如果我们需要查询一个路径 $5-4-2-1-3$ ，会发生什么事。那么首先把他转化成欧拉序上的一段，也就是 5 的最后一次出现位置，和 3 的第一次出现位置，那么把它所对应的那一段截取下来就应该是：$[5,6,6,7,7,4,2,3$] ，观察，我们发现这个路径上的点，在这段内容中，多了 6 和 7 但是他们出现次数都是偶数，不难想到用异或或者 vis 去重可以得到，其次是 1 号点，1 号点是 LCA 我们应该需要特殊计算。所以说大概的找找规律，可以知道大概的计算方式。接着就是按照这样的规则模拟即可。 最后有一个细节问题，欧拉序的大小是原来的两倍！ 例题讲解：孤舟斩蛟这里提供一道非常非常模板的题目：SP10707 就是在上述板子的基础上统计一波颜色即可 ...