逆元 费马小定理和逆元 在模运算中，逆元是一个非常重要的概念。如果 aaa 和 MODMODMOD 互质（即它们的最大公约数是 1），那么 aaa 在模 MODMODMOD 下的逆元 bbb 满足： ab≡1(modMOD)ab \equiv 1 \pmod{MOD} ab≡1(modMOD) 逆元实质上是乘法操作的“撤销”。在模 MODMODMOD 算术中，逆元使我们能够通过乘以逆元来“消除”一个数的影响，从而简化计算。 费马小定理告诉我们如何快速找到逆元，费马小定理是关于素数的一个定理，它提供了一种快速计算幂模的方法。如果 ppp 是一个素数，且 aaa 不是 ppp 的倍数，那么 ap−1a^{p-1}ap−1 被 ppp 除的余数总是 1。用数学语言来描述就是： ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p} ap−1≡1(modp) a∗ap−2≡1(modp)a * a^{p-2} \equiv 1 \pmod{p} a∗ap−2≡1(modp) a≡1/ap−2(modp)a \equiv 1 / a^{p-2} \pmod{p} a≡1/a ...

快速幂 在计算数的幂时，常规的做法是进行多次连乘运算，例如计算 a 的 n 次幂，就需要连乘 n 次：a a … * a。然而，当指数 n 很大时，这样的计算方式效率很低，会进行大量的重复计算。 快速幂算法（Exponentiation by Squaring）是一种优化计算幂的方法，它通过将指数 n 分解成二进制形式，并利用幂的性质进行计算，从而减少了不必要的重复计算，提高了计算效率。 模板 12345678910int MOD = (int)1e9 + 7;long pow(long x, int n) { long res = 1; while (n != 0) { if (n % 2 != 0) res = res * x % MOD; x = x * x % MOD; n /= 2; } return res;} 矩阵快速幂 12345678910111213141516171819202122232425private long[][] multi(long a[][] ...

字符串哈希 多项式字符串哈希：可以得到所有子串的哈希值 1234567891011121314151617// 多项式字符串哈希（方便计算子串哈希值）// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]char[] t = target.toCharArray();final int MOD = 1_070_777_777;final int BASE = (int) 8e8 + new Random().nextInt((int) 1e8); // 随机 base，防止 hackint[] powBase = new int[n + 1]; // powBase[i] = base^iint[] preHash = new int[n + 1]; // 前缀哈希值 preHash[i] = hash(target[0] 到 target[i-1])powBase[0] = 1;for (int i = 0; i < n; i++) { // 计算t ...

Manacher算法 Manacher算法是一种用于查找字符串中最长回文子串的高效算法，它的时间复杂度为O(n) 算法维护一个数组P，其中P[i]表示以位置i为中心的最长回文串的半径 Manacher算法利用了回文串的对称性来加速搜索过程。如果当前考虑的位置i在之前找到的最长回文串的范围内，那么可以利用这个回文串的对称性来确定i的位置的回文半径的初始值。如果i的位置超出了之前回文串的范围，那么需要从i的位置开始进行暴力匹配来确定回文半径 在算法执行过程中，会维护一个最右端点R，它表示当前找到的最长回文串的右端点。每次找到一个新的回文串时，都会更新R的位置 Manacher 算法可以计算以s[i]（或者s[i] 和 s[i+1]）为回文中心的最长回文子串的长度。 此外，还可以： 判断任意子串是否为回文串。 计算从𝑠[𝑖] 开始的最长回文子串的长度。 计算以𝑠[𝑖] 结尾的最长回文子串的长度。 1234567891011121314151617181920212223242526272829303132class Manacher { public int[ ...

滑动窗口 对于每个问题，由于子串越长，越满足要求，有单调性，所以可以用滑动窗口解决 2962. 统计最大元素出现至少 K 次的子数组: todo 3306. 元音辅音字符串计数 II: 恰好包含k个转换为至少包含k个 - 至少包含k+1个 3413. 收集连续 K 个袋子可以获得的最多硬币数量: 不重叠区间问题，边界处理，正反两次滑窗（构造逆序相反数数组）

0-1树 概念 0-1树是字典树的一个变种，每个树节点只有0和1两个孩子，可以用来维护一些数字的异或和。 相关题解 421. 数组中两个数的最大异或值 2935. 找出强数对的最大异或值 II(2349)

博弈dp 一人最大化得分，一人最小化得分 3283. 吃掉所有兵需要的最多移动次数

值域dp 利用值域作为状态进行dp，枚举值域 3277. 查询子数组最大异或值：https://bughere.github.io/algorithm/problem/algorithm-problem-leetcode-3277/

状压dp 3276. 选择矩阵中单元格的最大得分：状压矩阵行号 3283. 吃掉所有兵需要的最多移动次数：状压走过位置的集合 3533. 判断连接可整除性：状压选择的元素，用记忆化搜索实现dp 526. 优美的排列: 状压数组位置

区间dp 从数组的左右两端不断缩短，求解关于某段下标区间的最优值。 一般定义：f[i][j] 表示下标区间 [i, j] 的最优值。 最长回文子序列 516. 最长回文子序列 其它 5. 最长回文子串：记搜和递推两种写法 3040. 相同分数的最大操作数目 II(1709)：有点意思 3277. 查询子数组最大异或值：区间dp嵌套区间dp