逆元 费马小定理和逆元 在模运算中，逆元是一个非常重要的概念。如果 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[][] ...

哈希大法 枚举右维护左 对于双变量问题，例如两数之和 (a_i + a_j = t)，可以枚举右边的 (a_j)，转换成单变量问题。也就是在 (a_j) 左边查找是否有 (a_i = t - a_j)，这可以用哈希表维护。 用哈希记录之前的数，并用于判断情况是否成立 1. 两数之和：经典的枚举右维护左 421. 数组中两个数的最大异或值: 对于每一位bit，枚举右维护左 3381. 长度可被 K 整除的子数组的最大元素和: 枚举右维护之前每个余k索引的前缀和最小值 [3404. 统计特殊子序列的数目]：题目式子变形 + 枚举右维护左 二重哈希 第一个哈希的value被当作key放入第二个哈希 3092. 最高频率的 ID 字符串哈希 请看字符串哈希 前缀和+哈希表 请看前缀和 遍历过程维护集合大小 在遍历的过程中，我们可以通过前后双指针（滑动窗口），动态维护一个哈希表，来确保当前窗口的元素集合大小不超过某个值k，如下代码所示 12345678910111213for (int i = 0, j = 0; i < n; i++) { // 前后双指针+哈希表记录 ...

循环节 循环节：指在序列中出现的一种重复的、周期性的模式。这个模式可以是一组连续的元素，也可以是整个序列的重复。 周期性特征：序列中的循环节反映了序列的周期性特征，即序列中的某一段会以某种方式重复出现。 寻找循环节的方法 快慢指针法：用两个指针，一个每次走一步，另一个每次走两步。如果存在循环节，两个指针最终会相遇。 哈希表法：使用哈希表记录每次遍历的状态，如果发现某个状态已经出现过，说明存在循环节。 统计重复个数 定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。 例如，str == ["abc", 3] =="abcabcabc" 。 如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。 例如，根据定义，s1 = "abc" 可以从 s2 = "ab***dbe***c" 获得，仅需要删除加粗且用斜体标识的字符。 现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = ...

差分数组 1234a[0] a[1] a[2] a[3] a[4] (0)差分数组: a[0] a[1]-a[0] a[2]-a[1] a[3]-a[2] a[4]-a[3] (-a[4])对差分数组求前缀和: a[0] a[1] a[2] a[3] a[4] (0)// 考虑末尾0(-a[4])，那么差分数组之和sum=0 前缀和就是离散版本的“求积分”，差分数组就是离散版本的“求微分” 形成目标数组的子数组最少增加次数 给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。 请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则： 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。 答案保证在 32 位有符号整数以内。 示例 1： 1234567输入：target = [1,2,3,2,1]输出：3解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。[0,0,0,0,0] 将下标为 0 到 4 的元素（包 ...

前缀和 前缀和是一种数组变换方法，通过将数组中每个元素替换为从数组起始位置到当前位置的所有元素之和。这样，计算任意区间的和变得非常高效，只需一次前缀和计算即可，而不需要多次重复计算。 123int[] nums;int n = nums.length, sum[] = new int[n+1];sum[i+1] = sum[i] + nums[i]; 需要用sum[0]表示空数组的和 l到r的区间和表示为 sum[r+1] - sum[l] 例如，nums[0]到nums[5]的区间和表示为 sum[6] - sum[0] 二维前缀和 定义sum[i+1][j+1]表示左上角grid[0][0]，右下角grid[i][j]的子矩阵元素和 123456int[][] sum = new int[m + 1][n + 1];for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] ...

单调栈 单调栈(Monotonic Stack)是一种特殊的栈，它首先是一个栈，从栈顶添加和删除元素，其次栈中的所有元素单调递增或者单调递减 在一个队列Deque中，我们offer右边，poll左边，这样左边就是队首，右边是队尾 如果这个Deque作为栈，我们push和pop左边，并且把左边作为栈顶 单调性的判断是从栈顶到栈底（Deque中从左往右看） 单增栈：栈顶到栈底的元素是单调递增的，即栈顶的元素最小 单减栈：栈顶到栈底的元素是单调递减的，即栈顶的元素最大 后上界：对于数组中的某个元素 a[i]，它的后上界是指在它之后的第一个比它大的元素 后下界：对于数组中的某个元素 a[i]，它的后下界是指在它之后的第一个比它小的元素 单调栈在算法中的应用在于它能够在一次扫描(从左到右)即O(n)的复杂度之内找到数组中每一个元素的后上界(单增栈)或者后下界(单减栈) 496. 下一个更大元素 II: 递增栈获得每个元素的后上界 2866. 美丽塔 II(2072) 1944. 队列中可以看到的人数(2105) 2454. 下一个更大元素 IV(2175)：双单调栈 ...

dp深似海 “系统过去的历史只能通过现阶段的状态去影响系统的未来”——研究生算法课程老师对动态规划的描述，感觉挺不错的 分类参考了灵神的dp题单 记忆化搜索和递推是dp的两种实现方式 网格图dp 背包dp 线性dp 状态机dp 划分型dp 区间dp 状压dp 数位dp 树形dp dp回溯 其它待分类dp 注意事项 如果动态转移方程不是按顺序的，那么需要注意不能直接赋值f[i+1][j] = f[i][j];，因为这样可能会覆盖之前动态转移的结果（注释的是按顺序的动态转移写法） 相关题解：3276. 选择矩阵中单元格的最大得分 1234567f[i+1][j] = Math.max(f[i+1][j], f[i][j]);// f[i+1][j] = f[i][j]; // 这里是错的，不能赋值for (int s = map.get(nums.get(i)), t = 0; s > 0; s -= t) { t = s & -s; if ((j & t) > 0) continue; f[i+1][j|t] = ...

组合计数 计数基本原理 ∣A∣=∑a∈A1|A| = \sum\limits_{a \in A} 1∣A∣=a∈A∑​1 加法定理 |A U B| = |A| + |B| 乘法定理 |A * B| = |A| * |B| 举例 n-bit二进制串一共有多少个： 2^n（乘法原理） 如果把0看作(，把1看作)，配对的括号序列有多少个？ 0011->(()) 101010->)()()( 对于长度为6的序列： 序列={()‾(()),k=2()‾()(),k=2(‾())‾(),k=4(‾(()))‾,k=6(‾()())‾,k=6序列 = \begin{cases} \underline{()}(()), & k = 2 \\ \underline{()}()(), & k = 2 \\ \underline{(}()\underline{)}(), & k = 4 \\ \underline{(}(())\underline{)}, & k = 6 \\ \underline{(}()()\underline{)}, & ...

LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例： 1234567891011121314151617输入["LRUCache", "put", "put", "get", "put", "get", "put", "get& ...