什么是最小树形图 最小树形图就是给定一个$n$个点的有向图，我们钦定一个根，现在要找$n-1$条边，在根能到达其他所有点的前提条件下，使得$n-1$条边的总长度尽可能小。 怎么找最小树形图 这里就得用到朱刘算法了。朱刘算法是一个$O(n \cdot m)$的算法。当然，还有Tarjan巨神的$O(nlogn)$的算法。但我太菜了，并学不会 图出自这里 上面这张图很好的诠释了朱刘算法的主要内...

为什么要学Kruskal重构树 有时候，题目让我们多次求一个图的两点路径上最小值最大/最大值最小是多少。这种时候，根据一个比较显然的结论，我们可以把问题搬到一颗最小/最大生成树里面去做。 这个时候，我们当然可以倍增来搞这个问题。但在这里，我想向大家引入一种新的数据结构，它是基于kruskal求生成树的算法改来的，因此被称为Kruskal重构树。 什么是Kruskal重构树 这张图可以一目了...

为什么要学左偏树 有时候，某些题目要求我们合并两个堆。 合并两个堆，大家都知道可以用splay暴力启发式合并处理。很不幸的是，这玩意的复杂度是$O(nlog^2n)$的，在一些毒瘤题目专门考可并堆的题目中，是注定要被卡的。 可并堆系列算法可以很优雅的解决这系列的算法，她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。 什么是左偏树 正如她字面...

什么是FFT FFT是用来快速计算两个多项式相乘的一种算法。 如果我们暴力计算两个多项式相乘，复杂度必然是$O(n^2)$的，而FFT可以将复杂度降至$O(nlogn)$ 如何FFT 要学习FFT,我们得先了解它的思想。 首先，我们得先了解如何表示一个多项式。显然，我们最传统的方法表示多项式就是表示它的系数就好。但是，如果我们用系数来计算两个多项式相乘，复杂度无论如何都是$O(n^2)$的。...

本菜鸡尚未学会第二类斯特林数，请各位dalao不要相信本文的任何一个字 什么是第二类斯特林数 在组合数学，Stirling数可指两类数，第一类Stirling数和第二类Stirling数，都是由18世纪数学家James Stirling提出的。 Stirling数有两种，第一类和第二类Stirling数，它们自18世纪以来一直吸引许多数学家的兴趣，如欧拉、柯西、西尔沃斯特和凯莱等。后来...

题面 传送门：POJ Solution 就是裸的扩展中国剩余定理嘛qwq 注意几点：一定要时时刻刻去膜取模，否则一定会爆long long，尤其是算出来的$k_0$ 这里给出几组易锅数据：(第三组容易爆long long) input: 1234567891011121314151617418373 161478614 149488440 1748022751 21618619576 81...

为什么要扩展中国剩余定理？ 建议学习前置芝士：中国剩余定理（不学也不要紧，因为并没有啥关系） 我们知道，中国剩余定理是用来解线性同余方程组的算法，类似下面这个： $x \equiv a_0 (p_0)$ $x \equiv a_1 (p_1)$ $x \equiv a_2 (p_2)$ 很不幸，这里要求$p_0,p_1,p_2$两两互质 . 如果不互质怎么办？当然是把出题者拖出去吊起来打啊。...

为啥要学LCT啊 在开坑之间，我们来先看一段对话： Q：给你一颗森林，现在不断的连接森林中的两棵树，保证不连出环，多次问你某两个点的连通性？ A（dalao&蒟蒻）：这不是SB题吗？显然并查集水过啊。 Q：说的好，但是如果我要删除某些边呢？ A（dalao）：那就可持久化并查集啊，你的问题怎么那么水。 A（蒟蒻）：…（发出gg的声音） 这时候，如果我们并不想写可持久化并查集的话，就得...

什么是淀粉质点分治？ 就是把分治搬到树上，以某个点为根，分别分治处理子树的答案，再计算子树与子树间的答案的玄学算法。 举个例子： 如何求出一颗树上距离为K且所经过的点最少的点对？ 对于这种题，我们可以把某个点（一般为重心）作为根，然后对左右子树递归处理，先分别得出左右子树的答案，再求出横跨两个子树之间的点对的答案。 为什么要学淀粉质 对于上面那道题，如果我们用传统的暴力做法，最优的复杂度只能...

什么是裴蜀定理 裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约 数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。 ——百度百科 用人话来说就是： $\sum a_i*...