本文源自计蒜客课件，切勿外传！

扩展 KMP 能在 $O(|S|+|T|)$ 时间复杂度内处理出字符串 $S$ 的所有后缀与字符串 $T$ 的最长公共前缀。

之所以称为扩展 KMP，是因为其思想和 KMP 算法很类似。

离散傅里叶变换（Discrete Fourier Transform，缩写为 DFT），是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其 DTFT 的频域采样。

FFT 是一种 DFT 的高效算法，称为快速傅立叶变换（Fast Fourier transform）。

快速数论变换 (NTT) 是快速傅里叶变换（FFT）在数论基础上的实现。

重新学习了高斯消元，当然也要重写一篇啦。

占坑，先咕。

点分治

概述

点分治适合处理大规模的树上路径信息问题。

点分治的实现基于以下结论：一棵子树上的任意一条路径，要么经过树根，要么被完全包含在树根的一棵子树中。

定义 $solve()$ 函数，对每棵子树进行分值处理，并保证 $O(n\log n)$ 的时间复杂度。

概述

在处理某些树上问题时，并非树上的所有节点都起作用；这时可以借助虚树，将树上重要的点构造成一棵树，在虚树上处理问题，优化时间复杂度。

概述

如果题目中定义一种等价关系，满足等价关系的元素被看成同一类，只统计一次；这样的问题称为等价类计数问题。一般的等价类计数问题可以用 Burnside 引理或 Pólya定理解决。

刚复习了一遍 qwq 我当时写得真好