中国剩余定理（$\textbf{CRT}$）解决问题类型例题：洛谷 P1495 【模板】中国剩余定理（CRT）（本题需要使用 快速乘，否则超出 unsigned long long 的存储范围）。 给定 $n$ 个两两互质的正整数，构成序列 $\{...

高次不等式画图，一般都问与 $0$（即 $x$ 轴）的关系。 对于函数$$ y=\prod\limits_{i=1}^{n}(x-a_i)^p_i $$我们可以先得到其与 $x$ 轴的交点：$a_1,a_2,\cdots,a_n$​。 判断穿的方向假...

裴蜀定理形式 若 $a,b\in\mathbb{Z}$，那么对于 $\forall x,y\in\mathbb{Z}$，$\gcd(a,b)\mid a\times x+b\times y$。 此外，一定 $\exist\,x,y \in \math...

众所周知： 线段树的代码长，常数大； 树状数组的代码短，常数小，甚至可以通过 $10^6$ 量级的数据。 所以，能不能实现一个可以区间修改、区间查询的树状数组呢？ 由于涉及区间操作，考虑差分数组 $\{d_n\}$。 区间修改对于原数组 $[l...

取模定义对于 $a,b\in\mathbb{Z}$，满足 $b>0$，则存在唯一的整数 $q,r$，满足 $a=b\times q+r\,(0\le r

定义排列从 $n$ 个不同的元素中，任取 $m$ 个元素按照一定的顺序构成一个序列的方案数，叫做从 $n$ 个元素中取出 $m$ 个元素的排列数。 排列数记为 $A(n,m)$ 或 $A_{n}^{m}$。 组合从 $n$ 个不同的元素中，任取 $m...

逆元定义如果 $ax\equiv 1\pmod p$，则称 $x$ 为 $a$ 在模 $p$​ 意义下的乘法逆元。 逆元存在当且仅当 $a\perp p$，即 $\gcd(a,p)=1$​。 将 $ax\equiv 1\pmod p$ 转化可得 $x...

由来珂朵莉树（$\text{Chtholly Tree}$），又称老司机树（$\text{Old Driver Tree}$，$\textbf{ODT}$）。 源于 Codeforces Round 449 (Div. 1) 的 C 题 CF896C...

Splay 树定义Splay 树是一个二叉平衡搜索树，它可以通过 Splay 操作 将一个结点旋转至根结点或者一个给定的结点的下一层，使得整棵树仍然满足二叉搜索树的性质。 Splay 树可以在均摊 $O(\log n)$ 的时间内完成查找、插入、查询...

基本知识树链剖分是一种可以将树上问题转化为序列问题的思想，将树分割为若干条链，以维护树上的路径信息。 树链剖分有多种形式，例如重链剖分，长链剖分，实链剖分。本文主要介绍重链剖分。 基本定义重子节点： 预备数组fa[u]，存储 $u$ 的父亲节点。 d...