题面 传送门：SPOJ 694 Solution 这题可以用SAM来搞，也可以用SA来搞。但无论是哪种搞法，都是基本操作。下面我们来分别讲解一下怎么搞。 SAM 这题用SAM来求就十分粗暴简单。不会SAM的小伙伴可以戳这里 首先，我们先把SAM建出来。根据SAM的性质，我们从出发点随着SAM任意走，走到哪里都是一个完全不同的子串。因此，我们只需要对SAM做一个拓扑序DP/记忆化搜索即可求出...

题面 洛谷 P2743 Solution 这题可以用哈希做，也可以用SA做。下面我们分别讲一下两种做法。 哈希 首先，我们把转掉的问题处理掉。我们考虑把原串做差分数组，即用后面那一个减去前面那一个。这样子，我们直接在新的串上找完全相同的两个不可重叠子串即可。 这个，我们考虑先在外面二分一个答案的长度，然后暴力做，从后往前扫，把所有子串都丢到哈希表里面，插入一个新的串之前，就检查一下之前是否...

题面 传送门：洛谷P2852 Solution 首先，我们阅读题面可以发现题目让我们求出一个出现次数>k的可重复的子串。 这玩意我们可以用SA求，也可以用SAM求。 SA 这题用SA做就比较妙，首先我们显然要求把SA及height求出来。 因为两个后缀的LCP是它们之间的height的min，我们可以利用这个性质。 考虑一个子串，它所能“控制”的区间的所有的height都必须比它大。...

为什么要学后缀数组 为了解决一类字符串神题妙题。 什么是后缀数组 什么是后缀 要理解什么是后缀数组，首先要明白什么是后缀。 一个字符串$[S_1:S_n]$的后缀为:$[S_i:S_n],i∈[1,n]$ 用人话来说，就是从每个字符开始到这个字符串的结尾所组成的串均为这个字符串的后缀。 例如： 假设我现在有一个字符串“abaaba”,那么。她的后缀有：a,ba,aba,aaba,baaba...

什么是基数排序 基数排序是一个时间复杂度为：$O(n*MAXNUM/base)$，空间复杂度为$O(base+n)$的优秀排序算法。 基数排序有什么用 我们知道，桶排序可以在$O(MAXNUM)$的时间内，$O(MAXNUM)$的空间内排序一个数组，快速排序可以在$O(nlogn)$的时间内，$O(n)$的空间内排序一个数组。 如果有一个排序任务的最大数字比桶大，而数字数量又爆多怎么办？这时...

为什么要学左偏树 有时候，某些题目要求我们合并两个堆。 合并两个堆，大家都知道可以用splay暴力启发式合并处理。很不幸的是，这玩意的复杂度是$O(nlog^2n)$的，在一些毒瘤题目专门考可并堆的题目中，是注定要被卡的。 可并堆系列算法可以很优雅的解决这系列的算法，她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。 什么是左偏树 正如她字面...

题面 洛咕 Solution 题目要求求出区间众数，强制在线。 区间众数是一个比较尴尬的问题，我们无法用区间数据结构来处理这个问题，因为我们没法很好的合并区间众数的答案。 既然区间数据结构解决不了这个问题，我们可以考虑一下使用基于分块的算法，例如莫队。 这题用莫队非常好处理，不幸的是，这题要求强制在线。 因此我们考虑使用分块算法。 分块算法的核心在于把一整个块的信息压缩起来以便快速处理。 ...

题面 传送门：洛咕 Solution 调到自闭，我好菜啊 为了方便讨论，以下式子$m>=n$ 为了方便书写，以下式子中的除号均为向下取整 我们来颓柿子吧qwq 显然，题目让我们求： $\large \sum_{i=1}^n\sum_{j=1}^m lcm(i,j)$ $lcm$没法玩，我们转到$gcd$形式： $\large \sum_{i=1}^n\sum_{j=1}^m \fra...

题面 传送门：洛咕 Solution 我怎么只会刷水题 这题的双倍经验题，不多说啥了。 啥？范围不一样？ 那根据我们写数位DP及二维前缀和的经验，我们容斥一下… 然后就没有然后了。 时间复杂度$O(m*\sqrt n)$ Code 人傻自带大常数,不开O2 T一个点 事实上这题可以把一些不必要的$longlong$改成$int$，刚好能过。可惜我太颓，不想改了 1234567891011...

题面： 传送门：洛咕 Solution 首先，我们需要一个结论： $\large d(i,j)=\sum_{xi}\sum_{yj}[gcd(x,y)=1]$ 证明 理性证明请看这篇博客的例五 本蒟蒻提供一个感性证明的方法：如果$x*y$是$i*j$的因数，我们必须有$xi,yj$，而后面那个$gcd(x,y)$是用来去重的 有了这个柿子之后，我们之后的推导就比较套路了： 为了方便讨论...