CF367E 题解 CF367E 题解 有 $n$ 个区间，你需要为每个区间分配左右端点$l$，$r$ ($1 \le l \le r \le m$)，使得区间两两互不包含且至少存在一个区间的左端点等于 $x$，输出方案数对 $10^9 + 7$ 取模的结果。 $1 \le n,m \le 10^5$, $1 \le x \le m$。 若 $n >m$ 肯定无解，因为一定存在两个左端点相同的区间，而这两个区 2021-11-09 题解 codeforces dp
线段树合并学习笔记 线段树合并学习笔记前置芝士动态开点线段树一般我们写线段树都是在刚开始调用一个 build 函数建立出所有节点。但实际上有很多节点并没有保存信息，这些节点是多余的。所以就有的动态开点线段树，只有在用到时才建立这个节点，这种思想节省了很多空间，节点与节点之间的灵活性也更高，为线段树合并和主席树等算法提供了基础。我们简单了解一下动态开点线段树的代码实现。 线段树节点不同于普通线段树，需要存储左右孩子的位 2021-11-08 算法 模板 数据结构 线段树 线段树合并
三元环计数问题 三元环计数问题 link，给定一个无向图，求其中三元环的数量。 $1 \le n \le 10^5$，$1 \le m \le 2 \times 10^5$ 。 构造一个这样的有向图：对于原来图中的每一条无向边，改为由度数小的向度数大的连边，若相等则由编号小的向编号大的连边，在这样的图中，三元环 ${ x,y,z}$ ，度数最小或编号最小的点回向另外两点连边，所以边肯定是 $x \right 2021-11-06 算法 图论 三元环计数
P3306 题解 P3306 题解 link，给出 $p$，$a$，$b$，$x_1$，求第一个 $x_i = t$。 $x_{i + 1} \equiv a \times x_i + b \pmod{p}$ 。 $0 \le a, b, x1, t < p$，$2 \le p \le 10^9$， $p$ 为质数。 推一波： X_{i + 1} \equiv a \times X_i + b \pm 2021-11-04 题解 数学
BSGS（大步小步）算法学习笔记 BSGS（大步小步）算法学习笔记前置芝士会取模运算就行啦！ 正文部分拔山盖世 $\tt{BSGS}$ 算法用于求解 $a^x \equiv b \pmod{p}, \ a \perp p$ 中 $x$ 的值。 设 $x = ti - j$，$t = \left \lceil \sqrt{p} \right \rceil$，$1 \le i \le t$，$0 \le j < t$。 然后简单 2021-11-04 算法 模板 数学 BSGS
exgcd（扩展欧几里得）学习笔记 exgcd（扩展欧几里得）学习笔记前置芝士 基础的模、整数运算； $\gcd$ 的求法，即 $\gcd(a, b) = \gcd(b,a \bmod b)$； 裴蜀定理，二元一次方程方程 $ax+by=c$ 有解的充要条件是 $\gcd(a, b) \mid c$； 正文部分$\tt{exgcd}$ 用于求出二元一次方程 $ax+by=c$ 的一组特解。 首先根据裴蜀定理，可以先判掉无解的情 2021-11-04 算法 模板 数学 exgcd
网络流 24 题 部分水题题解 网络流 24 题 部分题题解注：代码只给出主程序部分，网络流板子基本相同。 方格取数问题link 给定 $m$ 行 $n$ 列的网格，每个格中有数，你可以取任意个格子的数，但不能同时取相邻的格子（四联通），求取出数的和的最大值。 $1 \le n,m \le 100$，$1 \le a_{i, j} \le 10^5$。 考虑相邻的格子有什么性质，容易发现相邻的格子横纵坐标和的奇偶性相反。又因 2021-11-02 题解 图论 网络流 最大流 最小割 网络流 24 题
网络流学习笔记 网络流学习笔记注：笔者比较菜，许多证明没有给出，一些地方可能有误。 一些定义网络对于一张有向图 $G \in (V, E)$，有一个源点 $S \in V$ 和一个汇点 $T \in V$，每一条边 $(u, v) \in E$ 有一个限流 $c(u, v)$。特别的，$\forall (u, v) \notin E \ , \ c(u, v) = 0$。 网络流对于一个函数 $f(u, v 2021-11-01 算法 模板 图论 网络流 最大流 最小割
CF1383D 题解 CF1383D 题解题意给定一个长度为 $n$ 的序列 $a$，选出 $a$ 中的若干个元素使得和为零。 数据范围 ：$1 \le n \le 10^6$，$i - n \le a_i \le 1 - i$ 题解构造题，$i - n \le a_i \le 1 - i$，即 $1 \le i - a_i \le n$ 。我们让 $i$ 向 $i - a_i$ 连边，这样显然形成环的时候和就是 $0 2021-10-30 题解 图论 codeforces 构造
CF1391E 题解 CF1391E 题解题意给定一个无向图，从下面两个操作中选择一个完成： 输出一条长度不小于 $\lceil \frac{n}{2} \rceil$ 的链 选出至少 $\lceil \frac{n}{2} \rceil$ 个点，两两组成点对，使得任意两个点对 $4$ 个点的子图边数不超过 $2$。 题解构造题，求出无向图的一个 $\tt{dfs}$ 树，若存在点深度大于等于 $\lceil \f 2021-10-30 题解 图论 codeforces dfs