一个Oier

中国剩余定理（CRT） 解决问题类型 例题：洛谷 P1495 【模板】中国剩余定理（CRT）（本题需要使用 快速乘，否则超出 unsigned long long 的存储范围）。 给定 n 个两两互质的正整数，构成序列 {mn}。再给定序列 {an}， 有如下同余方程 求 x 的最小正整数解。 结论 令 ，。 然后考虑求出 Mi × pi + mi × qi = 1 的一组可行解 (pi, qi)。 由于 mi 两两互质，所以 Mi ⊥ mi，那么 gcd (Mi, mi) = 1。 根据裴蜀定理，该方程必然存在解，故使用 Exgcd 求解即可。 令 ei = Mi × pi，则 这就是 x 的最小正整数解。 证明 考虑 ei × ai 对 mj 取模的值，可以发现 (1) 式中，由于 ei = Mi × pi，而 Mi 是 mj 的倍数，所以结果为 0​。 (2) 式中，pi 和 qi 满足 Mi × pi + mi × qi = 1，等式两边对 mi 取模，即得 ei mod  mi = 1，再两边同乘 ai 就可以得证。 由此不难发现，将 代入第...

高次不等式 画图，一般都问与 0（即 x 轴）的关系。 对于函数 我们可以先得到其与 x 轴的交点：a1, a2, ⋯, an​。 判断穿的方向 假设当前 y = (2x − 1)(x − 1)(2x + 1)。 则其与 x 轴交点为 。 但是此时我们会有两种可能的情况： 1 那么哪条曲线时对的呢？ 可以代入值。 假设代入一个较大的值 x = 100，那么显然 2x − 1 > 0，x − 1 > 0，2x + 1 > 0，故函数值  > 0。 图中红色曲线显然 x = 100 时  > 0，紫色曲线则  < 0，故红色曲线正确。 最终我们也得出了 y = (2x − 1)(x − 1)(2x + 1) 的函数图像。 当然，手绘不会那么精准，但是判断函数值与 0 的关系是无妨的。 判断是否穿过 那么给上面的函数加上一个指数，y = (2x − 1)(x − 1)2(2x + 1)，那么函数会变成什么样呢？ 简单情况 令 y1 = x − 1​，则图像为： 2 此时函数穿过了点 (1, 0)。 令...

裴蜀定理 形式 若 a, b ∈ ℤ，那么对于 ∀x, y ∈ ℤ，gcd (a, b) ∣ a × x + b × y。 此外，一定 ，使得 a × x + b × y = gcd (a, b) 成立。 证明 证明第一点： 证明第二点： 设 a × x + b × y 的最小正整数值为 r，考虑证明 a mod  r = 0。 设 ，则可得 a mod  r = a − p × r​。 代入 r，得到 a mod  r = a − p × (a × x + b × y)。 进一步可得 a × (1 − p × x) + b × (−p × y)，这就是 ax′ + by′​ 的形式。 因为 0 ≤ a mod  r < r，且 r 为 a × x + b × y 的最小正整数值， 所以 a mod  r = 0，即 r 是 a 的因数。 同理可得 r 也是 b 的因数。 所以 r 是 a, b 的公因数，即 r ∣ gcd (a, b)。 又因为 a × x + b × y 都是 gcd (a, b) 的倍数，所以 gcd (a, b) ∣ r。 故...

众所周知： 线段树的代码长，常数大； 树状数组的代码短，常数小，甚至可以通过 106 量级的数据。 所以，能不能实现一个可以区间修改、区间查询的树状数组呢？ 由于涉及区间操作，考虑差分数组 {dn}。 区间修改 对于原数组 [l, r] 区间每个数加 w。 可以转化为两次单点修改，即 l 单点处加 +w，r + 1 单点处加 −w。 区间查询 对于原数组 [l, r] 区间求和。 显然 可以差分为两个 [1, u] 的前缀求和。 观察每一个 ，可以发现 所以 d1 的贡献为 u，d2 的贡献为 u − 1，d3 的贡献为 u − 2，……，du 的贡献为 1。 故可得 dk 的贡献为 u − j + 1。 发现 u + 1 的值是固定的，可以提取出来： 因此同时使用两个树状数组维护 {dn}、{n × dn} 即可，该技巧即为超级树状数组。 代码实现 12345678910111213141516171819202122232425typedef long long lint;lint sum(int p, lint *t) { // 查询 t 中 [1,p]...

取模 定义 对于 a, b ∈ ℤ，满足 b > 0，则存在唯一的整数 q, r，满足 a = b × q + r (0 ≤ r < b)。 称 q 为商、r 为余数。余数用 a mod  b 表示，在 C++ 中表示为 a % b。 性质 (a + b) mod  m = (a mod  m + b mod  m) mod  m。 (a − b) mod  m = (a mod  m − b mod  m) mod  m。 需要注意的是，a mod  m 可能小于 b mod  m，那么结果在 C++ 中计算的结果将是负数。 但是在数学中，负数取模的结果仍然是非负数，故在 C++ 中一般将其写作 (a % m - b % m + m) % m。 (a × b) mod  m = (a mod  m × b mod  m) mod  m。 PS：注意，(a ÷ b) mod  m = ((a mod  m) ÷ (b mod  m)) mod  m 这个等式不一定成立！ 反例：a = 12, b = 3, m = 6，(a ÷ b) mod  m = 4，而 ...

定义 排列 从 n 个不同的元素中，任取 m 个元素按照一定的顺序构成一个序列的方案数，叫做从 n 个元素中取出 m 个元素的排列数。 排列数记为 A(n, m) 或 Anm。 组合 从 n 个不同的元素中，任取 m 个元素无序构成一个集合的方案数，叫做从 n 个元素中取出 m 个元素的组合数。 组合数记为 C(n, m) 或 Cnm，最常用的是 。 计算公式 常见公式 数学证明 组合意义证明 从 n 个人中选取 m 个人留下，等同于 n 个人中选取 n − m 个人让他们离开。 数学证明 组合意义证明 从 n 个人中选取 m 个人留下，可以分两类讨论： 第 n 个人被选中了：此时还要从剩下的 n − 1 人中选取 m − 1 个人，故方案数为 。 第 n 个人没被选中：此时还要从剩下的 n − 1 人中选取 m 个人，故方案数为 。 综上，总方案数 。 证明 考虑从 n 个人中选出任意个留下（可以不选），询问有多少种方案。 对于每个人考虑，每个人有留下或者不留下两种情况，所以总方案数为 2n。 对于选的人考虑，枚举选出的人数...

逆元定义 如果 ax ≡ 1 (mod  p)，则称 x 为 a 在模 p​ 意义下的乘法逆元。 逆元存在当且仅当 a ⊥ p，即 gcd (a, p) = 1​。 将 ax ≡ 1 (mod  p) 转化可得 ，那么模意义下 t ÷ a 就相当于 t × x。 快速求单个数的逆元 快速幂 费马小定理 当 且 p ∈ ℙ 时，有 ap − 1 ≡ 1 (mod  p) 由此转化可得 a × ap − 2 ≡ 1 (mod  p)，此时就可以发现 ap − 2 即为 a 在模 p 意义下的乘法逆元。 此时可以用快速幂计算逆元，时间复杂度 O(log p)。 扩展欧几里得算法 Exgcd 也可以用于求逆元。 由裴蜀定理可知，若 a ⊥ p，则必然 ，使得 a × x + p × y = 1​ 成立。 容易发现，a × x + p × y = 1 ⇔ a × x ≡ 1 (mod  p)。 使用 exgcd 解出这个方程即可，时间复杂度 O(log p)。 线性求 1 ∼ n​ 的逆元 例题：loj #110. 乘法逆元。 现要求在 O(n) 的时间内，求出模...

由来 珂朵莉树（Chtholly Tree），又称老司机树（Old Driver Tree，ODT）。 源于 Codeforces Round 449 (Div. 1) 的 C 题 CF896C。 具体实现 注意：珂朵莉树不是数据结构，而是一种颜色段均摊的思想。 核心思想 对于一个区间中值相同的一个子串使用一个结点存储。 结点存储 首先，一个结点需要存储其左右端点，故定义 size_t l, r。 其次，由于将值相同的子串使用一个结点存储，那么结点就需要存储其维护的值，故定义 mutable _Tp w，其中 _Tp 是数据类型。 应该如何将大量结点存储呢？ 可以开一个 std::set 存储结点，在看了下文的两个操作后，就可以发现使用 std::set 是最优的，std::vector 更劣。 但是听说 std::vector 因为常数小模板题更快？ 代码见后。 一些解释 mutable 意为可变的，这样在遍历结点时可以 O(1) 修改迭代器所对应的值，而不用花费 O(log n)​ 的时间取出结点，修改后重新插入。 将小于号如此定义是为了让结点在...

Splay 树 定义 Splay 树是一个二叉平衡搜索树，它可以通过 Splay 操作 将一个结点旋转至根结点或者一个给定的结点的下一层，使得整棵树仍然满足二叉搜索树的性质。 Splay 树可以在均摊 O(log n) 的时间内完成查找、插入、查询、删除等操作。 二叉搜索树的定义： 空树是一个二叉搜索树； 根结点左子树中的结点权值均小于根结点的权值； 根结点右子树中的结点权值均大于根结点的权值； 根结点的左右子树均为二叉搜索树。 结构 在 Splay 中，一共需要维护如下信息： root：树的根结点编号。 tot：当前总共开了点的个数（Splay 树显然使用动态开点）。 fa[i]：结点 i 的父亲结点。 son[i][0/1]：结点 i 的左右儿子编号，左儿子为 son[i][0]，右儿子为 son[i][1]。 val[i]：结点 i 的权值。 cnt[i]：权值为 val[i] 的数字的出现个数。 siz[i]：结点 i 及其子树的大小。 基本操作 辅助函数 pushup(x)：合并左右儿子的信息（即大小），更新至当前结点。 get(x)：返回 0 表示 x...

基本知识 树链剖分是一种可以将树上问题转化为序列问题的思想，将树分割为若干条链，以维护树上的路径信息。 树链剖分有多种形式，例如重链剖分，长链剖分，实链剖分。本文主要介绍重链剖分。 基本定义 重子节点： 预备数组 fa[u]，存储 u 的父亲节点。 dep[u]，存储 u 在树中的深度。规定根节点的深度为 1。 siz[u]，存储以 u 为根的子树大小，包含 u 这个节点。 son[u]，存储 u 的重儿子，即 u 的所有儿子 v 中 sizev 最大的一个儿子。 top[u]，存储 u 节点所在的重链中深度最浅的节点（即重链的顶端）。 dfn[u]，存储 u 节点在 DFS 序中的位置。 rnk[u]，存储 DFS 序中的第 i 个位置对应在树上的编号。有 rnkdfnu = u。 两遍 DFS 例题讲解 树链剖分 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 【模板】重链剖分/树链剖分 模板题。 【模板】最近公共祖先（LCA） 【TJOI2015】 旅游