给定一张 nnn 个点 mmm 条边的带边权连通无向图，其中有 ppp 个点是特殊点。 对于每个特殊点，求出它到离它最近的其它特殊点的距离。 1≤n,m≤2×1051 \le n,m \le 2 \times 10^51≤n,m≤2×105，2≤p≤n2 \le p \le n2≤p≤n，1≤w≤1091 \le w \le 10^91≤w≤109 首先，在 Dijkstra\tt{Dijks

有 nnn 座城市，第 iii 座城市里宝石的交易价格为 aia_iai​。当你经过第 iii 座城市时，你可以以 aia_iai​的价格购买或卖出一个宝石。在任意时刻，你最多只能携带一个宝石。 有 mmm 次操作，操作分为两种： 询问依次经过 lll 到 rrr 的城市的城市能获得的最大收益。最后离开编号为 rrr 的城市时，身上不能携带宝石； 将 lll 到 rrr 的宝石价格修改为

link 一个点集 S=(xi,yi)S = (x_i, y_i)S=(xi​,yi​) 的张集定义如下： 刚开始张集等于 SSS； 若对于点 (x,y)(x, y)(x,y) ，存在 (a,b)(a, b)(a,b)，使得 (a,b)(a, b)(a,b) 、 (a,y)(a, y)(a,y) 、 (x,b)(x, b)(x,b) 属于张集，则将 (x,y)(x, y)(x,y) 加入张集；

Atcoder ABC277G 题解 link 给定 nnn、kkk，求 CnkC_n^kCnk​ 的约数个数。 1≤n≤10121 \le n \le 10^{12}1≤n≤1012，1≤k≤min⁡(n,106)1 \le k \le \min (n, 10^6)1≤k≤min(n,106) 首先，一个数 $$n = \Pi_{i = 1}^{m} p_i^{k_i}$$ 的约数个数为

exCRT（扩展中国剩余定理）学习笔记 背景（？ 普通的 CRT 不能解决模数不互质的情况，按照数论算法的命名规则，能解决模数互质的算法就是 exCRT。 然鹅 exCRT 与 CRT 算法本身没有任何关系，个人觉得 exCRT 代码还更简单。 所以 CRT 有什么用？名字里有中国吗？ 前置芝士 exgcd（扩展欧几里得）； 一个简单的同余式转化，a≡bmod  p⇒a+kp=ba \eq

【模板】插头 dp 题解 link 给定一个 n×m​n \times m​n×m​ 的方格，有些格子不能铺线，其他格子必须铺，求构成一个闭合回的方案数。 $ 2 \le n,m \le 12$ 一个很显然的性质，因为是回路，所有要铺的格子都是一进一出两条线。 状态 考虑 dp，fi,j,sf_{i, j, s}fi,j,s​ 当前决策到第 iii 行第 jjj 个格子，状态为 sss 的

更快的输入输出！然而我没有写输出 看别人的 namespace io 都是一大坨，我自己精简了一下。 支持任意整形、字符串读入。（io::read</*想要读的类型*/>()） 原理很简单，在进行文件读入时 fread\tt{fread}fread 一次读入大量文件，具有较快的速度。 由于 fread\tt{fread}fread 是读文件的，所以在本地比较麻烦，不想用文件读入时可以把

主席树学习笔记 前置芝士 线段树 动态开店线段树 权值线段树 脑子 pvz 玩多了 用处 主席树即可持久化线段树，在线段树的基础上可以查询修改每个修改的内容并形成新的版本。 思想 如果每次修改后在建一棵线段树，空间复杂度肯定受不了。注意到线段树的一次修改操作最多影响 log⁡\loglog 个节点。因此我们可以只新建修改的节点，将原来的节点也用上，这样空间复杂度就是 Θ((n+q)lo

CF367E 题解 有 nnn 个区间，你需要为每个区间分配左右端点 lll，rrr (1≤l≤r≤m1 \le l \le r \le m1≤l≤r≤m)，使得区间两两互不包含且至少存在一个区间 的左端点等于 xxx，输出方案数对 109+710^9 + 7109+7 取模的结果。 1≤n,m≤1051 \le n,m \le 10^51≤n,m≤105, 1≤x≤m1 \le x \le

线段树合并学习笔记 前置芝士 动态开点线段树 一般我们写线段树都是在刚开始调用一个 build 函数建立出所有节点。但实际上有很多节点并没有保存信息，这些节点是多余的。所以就有的动态开点线段树，只有在用到时才建立这个节点，这种思想节省了很多空间，节点与节点之间的灵活性也更高，为线段树合并和主席树等算法提供了基础。我们简单了解一下动态开点线段树的代码实现。 线段树节点不同于普通线段树，需要存储