Posts

参考： 老师讲解 Fighting_Peter 的文章 其实Kruskal重构树并不难。 概览 首先，Kruskal重构树，顾名思义就是把整棵树重构。 并且其是基于Kruskal算法的。 它能解决很多问题，并且变种很多。 但我们先从基础的实现说起。 实现过程 我们考虑，在Kruskal算法里，我们每次会合并两个并查集集合。 准确来说是在两个点 $u$、$v$ 之间加一个边权为 $w$ 的无向边。 那么，我们就考虑，在重构树里，我们找到 $u$ 和 $v$ 分别所在的子树，把这两个子树的根拎出来，设为 $u’$ 和 $v’$。 然后，我们就新建一个点 $w$，然后把 $u’$ 和 $v’$ 的父亲设为 $w$。 此时我们就得到了另外一棵树。 比如说这个例子： 而在代码中，我们需要给这些方点一个别的编号，而不是以 $w$ 作为编号，否则会重，并且会炸。 特性 我们讲一些Kruskal重构树的特性： 这棵树一定是二叉树。 原树中的点放到重构树上一定是叶子，重构树上其他点都是原树中的边权。 节点个数一定是 $2n-1$，且 $2n-1$ 一定是根。 如果是最小生成树，那么这棵重构树一定是大根堆1，否则是小根堆。 原图中两个点 $u$、$v$ 之间所有路径上的边权最大值的最小值，就是该图的最小生成树重构树上，$u$ 和 $v$​ 的LCA的权值。 尚未想到证明方式 对于一个最小生成树上的点 $x$，其只通过（边权）不超过 $v$ 的边，能到的点集；和 $x$ 在重构树上深度最浅的、权值 $\leq v$ 的点 $y$ 的子树内（叶子）节点集合，是一样的。 这里稍微证明一下。 就是我们根据上面的性质，可以发现，设后者对应集合为 $S$，那么显然 $S$ 内的点，和 $x$ 点，的LCA的权值一定不超过 $v$，显然。 ...

（以下全部假设 $C_n^m$ 中的 $n$ 和 $m$ 都很大，最大能达到 $10^{18}$） Lucas定理 Lucas定理往往用于求组合数的结果且模数较小的题目。 其实定理很简单，也很好记，$\Large C_n^m=C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times \color{orange} C_{n \bmod p}^{m \bmod p}$，在 $p$ 为质数的条件成立。 上面之所以强调模数较小，是因为我们需要通过预处理阶乘的方式去求橙色项的值。 代码实现很简单，此处略。 但有个注意点，在我的代码模板里，由于求facny数组是递推求出的，而不是每个分别去用getny求出的，所以调用init函数时，传参应该是MOD-1而不是MOD。 exLucas定理 （前方高能） 这个定理还是解决求 $C_n^m \bmod p$ 的值的问题，$p$ 仍然很小，但不保证是质数。 根据M2579的做法，我们可以考虑对 $p$ 做一个唯一分解，分解成 ${p_1}^{a_1} \times {p_2}^{a_2} \times {p_3}^{a_3} \times \dots \times {p_k}^{a_k}$。 然后，分别求出 $C_n^m \bmod {p_1}^{a_1}$ 的值、$C_n^m \bmod {p_2}^{a_2}$ 的值、$C_n^m \bmod {p_3}^{a_3}$ 的值、…、$C_n^m \bmod {p_k}^{a_k}$ 的值，然后就可以用CRT求出 $C_n^m \bmod p$ 的值了。 在M2579内，$p$ 唯一分解后，每个 $a_i$ 都等于 $1$，所以直接用Lucas定理就可以求，但在一般的题目中，指数不一定都等于 $1$，所以才要用到exLucas定理。 ...

感谢这篇文章的作者。 wqs二分一般解决这类问题： 有 $n$ 个物品，你要选出恰好 $m$ 个（下称“选择物品个数限制”），可能有限制（下称“其他限制”），你要最大/小化某个权值。 但除此之外，还有一些限制： 如果我们设 $g_i$ 为选出恰好 $i$ 个时的最大/小权值，那么 $g$ 函数就应该是上凸（求最大权值）/下凹（求最小权值）的，即斜率单调递减（上凸）/递增（下凹）。 一般来说，如果没有任何限制（包括选择物品个数限制和其他限制），那么答案是很好求的。 一般来说，如果没有其他限制，那么选择物品数量越多，最小权值就越大/小。 以下是P5633的题解，顺带着讲了wqs二分的原理和应用。 在原题中，我们可以以标号为 $s$ 点在最小生成树上的出度为横坐标，以这个出度对应的答案为纵坐标，画出图像：（网上粘的图，只画了部分横坐标的情况） 显然D和E点就是最小值点。 接下来就是wqs二分的重点了 wqs二分也是二分，那它二分什么值呢，它二分的是斜率 $mid$。 具体而言，一个斜率就对应若干条平行的边，而总有一条边是完全切这个凸包的，如 $mid=-1$ 的时候，上图中被且的那个点就刚好是C点： 如果我们设题目要求 $s$ 的度数要恰好为 $6$，那么 $mid=-1$ 的时候被切的那个点C的纵坐标就是答案了。 但此时我们就有两个问题了： 如何求出被切的那个点的下标？ 就算求出了下标，那这个点的纵坐标又如何计算？ 接下来我们来解决这两个问题。 首先，这个切线肯定是所有经过某个点且斜率等于 $mid$ 的直线中截距最小的点： 具体地，根据切线的性质，在上述例子中，经过C点的斜率等于 $mid$ 的直线（即切线），与经过D点的斜率等于 $mid$ 的直线、经过E点的斜率等于 $mid$ 的直线相比，切线的截距肯定最小，后两者的截距肯定更大。 其次，显然，经过点 $(x,y)$ 且斜率等于 $k$ 的直线（肯定唯一），其截距一定等于 $y-kx$（$y=kx+b$，$b=y-kx$）。 而在二分的calc函数（此处不是check函数了，calc函数的返回值、返回值含义以及应用见下）中，我们已经知道了上述公式中的 $k$ 了（$k=mid$），所以我们只要让 $y-kx$ 最小、斜率为 $k$ 且经过了某个图上的点即可。 考虑到上述公式中的 $x$ 未知，所以我们可以干脆把所有 $s$ 的出边的边权都减 $mid$。（关于是加、减还是都彳亍的问题存疑） ...

下面是三道与博弈论相关的题目及其做法。 题目1：皮肤病 题面 （改编自《不可思议事件簿 第5册 魔法学院》，由艾教提供变体） （原题名称：加试难题） 在一个学校内，共有 $100$ 个人，每个人都养了一只狗。 但由于某些原因，校长确定了这 $100$ 条狗内，必然存在至少一条狗有皮肤病。 现在那些学生要确定一下哪些狗有皮肤病。 他们准备这样确定： 每天上午的时候，所有人看一下除了自己的狗之外的所有狗。 如果确认自己的狗病了，就在晚上敲一下宠物房内的钟。 现在已知： 无论谁，看那只狗，都能立刻确认它是否有皮肤病。 假设皮肤病不会对狗的寿命造成影响，即所有的狗都不会死亡。 皮肤病不能传染，并且忽略“人患病”造成的影响。 所有人都绝顶聪明（废话 并且： 第 $1$ 天晚上，没有钟声响起。 第 $2$ 天晚上，没有钟声响起。 第 $3$ 天晚上，没有钟声响起。 … 直到第 $10$ 天晚上，终于有钟声响起了。 请问： 那天晚上，共有多少人共同敲响了钟？ 在第 $10$ 天后，除了那些敲钟的人养的狗，是否会存在其他病了的狗？ 答案 $10$ 个人 不会 题解 我们考虑一下，如果说第 $1$ 天晚上有人敲钟，那么代表啥。 我们从人的角度考虑，如果说一个人发现其他狗都是好狗（指没有皮肤病的狗），那么必然自己的狗有皮肤病 （除了自己的，还有谁的？难不成是他自己？）。 这种情况下，他便会去敲钟。 但第 $1$ 天晚上没有钟声，所以每个人都观察到了至少 $1$ 个病狗，也就是说至少有 $2$ 个病狗。 随后第 $2$ 天，如果说一个人观察到其他的狗内，只有 $1$ 个病狗，那么显然自己的狗也得有皮肤病。 ...

点分治和树剖有一个相同点，就是算法都是从暴力经过一小步优化而来，但就是这一小步，让算法复杂度有了质的飞跃。 下面来讲一下这个算法的原理。 概览 其实“点分治”也是一个名不副实的算法，看完下面的讲述你就会发现这个算法根“分治”几乎无关。 点分治是专门解决树上路径统计的一种算法（树剖则是解决对树上路径的判断的算法）。 点分治的思想很朴素，就是DFS一下 $\text{lca}$ 的节点编号 $x$，然后统计 $\text{lca}$ 值刚好为 $x$ 的、满足题目条件的路径的数量，并累加到答案。 但直接进行统计还是炸裂的，点分治则是对这种统计方式做了一步优化 解决题型 上面说了，「点分治是专门解决树上路径统计的一种算法」，但并不是所有的树上路径统计都可以用点分治解决。 其实看完下面的实现，你就能知道它解决什么类问题，不过这里还是说一下。 就是首先，这个条件是形如“总和比某个值低”、“总和是某个值的倍数”等“可累加”的条件。 其中“可累加”指的是，如果知道了 $A$ 部分的某个值，和 $B$ 部分的某个值，那么 $A$ 和 $B$ 部分合并后的部分是否合法也一定知道。 但其他的条件目前还没有太明确，得自己去总结。 算法实现 下面说一下点分治的实现。 大体思路 我们拿“路径长度（路径上的边的边权之和）刚好为 $k$”问题举例。 注：原题链接P3806 就是我们考虑，当DFS到某个点 $x$ 的时候，就如上所说，设 $x$ 为 $\text{lca}$ 值。 然后，我们按顺序遍历所有子节点 $to$。 由于只要两个点 $y$、$z$ 满足 $y$ 和 $z$ 分别在 $x$ 的两个不同儿子及其子树内，那么 $\text{lca}(y,z)=x$。 并且所有满足条件 $\text{lca}(y,z)=x$ 的对 $(y,z)$ 只有满足上述条件的对。 所以，我们可以通过（另一种）DFS（方式）求出 $to$ 到 ( 所有 $to$ 及其子树内的点 ) 之间的距离（加上 $x \to to$ 的边权）的集合 $T$。 ...

基尔霍夫矩阵是用来求解生成树计数、求（权值）和相关题目的利器。 0. 求完全图的生成树数量（Prufer序列） 要说基尔霍夫矩阵，就要从一道题目说起： 给你 $n$，问 $n$ 个节点组成的无向无根树有多少种。 这道题可以用Prufer序列去做。 这里简单说一下Prufer序列的求法： 对于一张无向无根树，重复执行以下操作直到只剩 $2$ 个或更少的点，最后得到的那个序列 $a$ 就是这棵树的Prufer序列： 我们找到此时度为 $1$ 的节点，若有多个，找编号最小的，设找到的节点编号为 $x$。 在 $a$ 的末尾添加：与 $x$ 有连边的那个唯一节点。 删除 $x$。 Prufer序列别看求法非常简单，也没啥容易发现的性质，其实用处很大。 Prufer序列满足一个性质，就是，所有无向无根树，都可以唯一地对应一个Prufer序列；所有Prufer序列都可以唯一地对应一棵树。 所以，这道题就有解了，答案其实就是长为 $n-2$ 的Prufer序列有多少种。 由于Prufer序列的每个元素的值都是从 $1$ 到 $n$ 的，所以答案就是 $n^{n-2}$，显然。 1.1. 求任意无向图的生成树数量（基尔霍夫矩阵） 但如果把题目变化一下，就不能用Prufer序列去求了： 给你一张 $n$ 个节点 $m$ 条边的无向图，问这张图的生成树有多少个。 这题要用基尔霍夫矩阵。 具体地，我们定义 $D$ 矩阵，求法： $ D_{i,j}= \begin{cases} 0 & i \not= j \ \text{deg}(i) & i=j \end{cases} $ 其中，$\text{deg}(i)$ 代表这张图上 $i$ 的度是多少。 ...

按照正常的思路我们都直接将算法，但这会先讲一道题，然后再讲它的定义和求法。 参考： ABC335G题解 阶和原根 背景 是一场ABC335里的G题，当时在赛场上大概留了一个多小时的时间，但一直都在想用BSGS，但显然最后没想出来。 而这题的瓶颈就在下面问题： 对于两个数 $a,b$，是否存在一个 $x$ 使得同余方程 $a^x \equiv b \pmod p$ 有解。 $a,b,p \leq 10^{13}$（原题数据范围） 大家看到的第一眼显然可以用BSGS求。 但这个算法是 $O(\sqrt p)$ 的（如果涉及到具体实现的话，可能还得乘个 $\log \sqrt p$，就是set、lower_bound查找的复杂度），比较适用于单组询问，很难推广应用。 所以还有另外一种方式，比较适用于多组询问。 是我们求出来 $a$ 和 $b$ 的阶，即 $\text{ord}_p a$ 和 $\text{ord}_p b$，看 $\text{ord}_p b$ 是否是 $\text{ord}_p a$ 的因子（$\text{ord}_p b \mid \text{ord}_p a$）即可。 这里先不证这个结论是否正确，但相信大家第一次看到“阶”的时候定然是一头雾水的，下面我就来说一下它的定义和求法。 定义 阶 阶的话，跟逆元相似，还是需要两个值，只不过这里叫做“$a$ 在模 $p$ 意义下的阶”而已，换汤不换料。 这个表示方法就是 $\text{ord}_p a$。 它的定义是： 给你整数 $a$、$p$。 找到最小的 $x$，使得同余方程 $a^x \equiv 1 \pmod p$ 成立。 这个 $x$，就是$a$ 在模 $p$ 意义下的阶。 原根 但说到阶，我们定要讲一下它的孪生兄弟，原根了。 ...

二维决策单调性 对于形如 $d_{i,j}=\min\limits_{k=0}^{i-1} \Big( d_{k,j-1}+w(k+1,i) \Big)$ 的方程，我们尝试记录 $f_{i,j}$ 代表 $d_{i,j}$ 的最优转移点（$k$ 变量），如果有 $f_{i,j-1} \leq f_{i,j} \leq f_{i+1,j}$，那么就是经典的四边形不等式优化，复杂度为 $O(n^2)$，证明此处略（在"四边形不等式相关.md"里有）。 但是，如果只有 $f_{i,j} \leq f_{i+1,j}$，那么就不能用四边形不等式优化了，需要用分治的方式优化。 具体地，我们从小到大枚举 $j$，然后转移所有的 $d_{i,j}$。 定义分治函数dp(l,r,jl,jr)代表我们要转移所有的 $d_{i,j}$（$l \leq i \leq r$），并且保证所有在本次分治转移范围内的 $d_{i,j}$ 的转移点 $f_{i,j}$ 都在 $[jl,jr]$ 内。 我们可以先求出 $[l,r]$ 的中点 $mid$，然后转移 $d_{mid,j}$：暴力枚举转移点 $k$（当然，要在 $[jl,jr]$ 内）进行转移，并递归dp(l,mid-1,jl,最终转移点)和dp(mid+1,r,最终转移点,jr)。 该算法复杂度为 $O(n^2 \log n)$，证明： 首先，枚举 $j$ 的复杂度 $O(n)$。 其次，只看 $[jl,jr]$，$[jl,jr]$ 在递归的过程中就形成了个线段树的类似结构，只不过单层内可能有部分重叠位置，而且划分点（上面说的“最终转移点”）可能不是中点，不过无关紧要。 然后，再看 $[l,r]$，$[l,r]$ 在递归过程中也形成了类似于线段树的结构，并且易证这个递归树深度是不会超过 $\log n$ 的。 有了深度的保证，而且一层内的 $[jl,jr]$ 区间长度和最多只有 $O(n)$ 级别，所以一次分治的复杂度就是 $O(n \log n)$。 ...

来源：ABC372G官方题解 贡献：OI Wiki 这个算法确实挺妙的，所以我就写个笔记。 定义 这个算法需要用到一个函数： $$ f(a,b,c,n)=\sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a\color{default}i+\color{blue}b\color{default}}{\color{green}c\color{default}} \right\rfloor $$ 在下面参数 $a$、$b$、$c$ 都会用三种颜色标出，以便于区分。 因为 $a$、$b$、$c$、$n$ 都很大，所以我们没法直接暴力求。 数论分块显然也不彳亍。 所以我们只能另辟蹊径了。 求值 咱从简单到复杂走。 1 首先，我们可以知道： $$ \begin{aligned} f(a,b,c,n)&=\sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a\color{default}i+\color{blue}b\color{default}}{\color{green}c\color{default}} \right\rfloor \ &=\sum\limits_{i=0}^n \left\lfloor \dfrac{(\lfloor \frac{a}{c} \rfloor c + a \bmod c)i+(\lfloor \frac{b}{c} \rfloor c + b \bmod c)}{c} \right\rfloor \ &=\sum\limits_{i=0}^n \left\lfloor \dfrac{\lfloor \frac{a}{c} \rfloor c \cdot i + a \bmod c \cdot i+\lfloor \frac{b}{c} \rfloor c + b \bmod c}{c} \right\rfloor \ &=\sum\limits_{i=0}^n \left( \left\lfloor \frac{a}{c} \right\rfloor i + \left\lfloor \frac{b}{c} \right\rfloor + \left\lfloor \dfrac{a \bmod c \cdot i+b \bmod c}{c} \right\rfloor \right) \ &=\dfrac{n(n+1)}{2} \left\lfloor \frac{a}{c} \right\rfloor + (n+1) \left\lfloor \frac{b}{c} \right\rfloor + \sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a \bmod c\color{default} \cdot i+\color{blue}b \bmod c\color{default}}{\color{green}c\color{default}} \right\rfloor \ &=\dfrac{n(n+1)}{2} \left\lfloor \frac{a}{c} \right\rfloor + (n+1) \left\lfloor \frac{b}{c} \right\rfloor + f(a \bmod c,b \bmod c,c,n) \ \end{aligned} $$ ...