什么是最小树形图 最小树形图就是给定一个$n$个点的有向图，我们钦定一个根，现在要找$n-1$条边，在根能到达其他所有点的前提条件下，使得$n-1$条边的总长度尽可能小。 怎么找最小树形图 这里就得用到朱刘算法了。朱刘算法是一个$O(n \cdot m)$的算法。当然，还有Tarjan巨神的$O(nlogn)$的算法。但我太菜了，并学不会 图出自这里 上面这张图很好的诠释了朱刘算法的主要内容： 我们算法主要有以下几个步骤： 找到到达每个点的长度最小的入边（根节点不找） 这些边如果连成一颗树则结束； 如果这些边中除了…

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

为什么要学后缀数组 为了解决一类字符串神题妙题。 什么是后缀数组 什么是后缀 要理解什么是后缀数组，首先要明白什么是后缀。 一个字符串$[S_1:S_n]$的后缀为:$[S_i:S_n],i∈[1,n]$ 用人话来说，就是从每个字符开始到这个字符串的结尾所组成的串均为这个字符串的后缀。 例如：假设我现在有一个字符串“abaaba”,那么。她的后缀有：a,ba,aba,aaba,baaba,abaaba。 什么是后缀数组 把所有后缀按字典序排序之后所构成的数组。 例如：假设我现在有一个字符串“abaaba”,那么。她…

什么是基数排序 基数排序是一个时间复杂度为：$O(n*MAXNUM/base)$，空间复杂度为$O(base+n)$的优秀排序算法。 基数排序有什么用 我们知道，桶排序可以在$O(MAXNUM)$的时间内，$O(MAXNUM)$的空间内排序一个数组，快速排序可以在$O(nlogn)$的时间内，$O(n)$的空间内排序一个数组。 如果有一个排序任务的最大数字比桶大，而数字数量又爆多怎么办？这时候，时空复杂度基于这两者之间的优秀排序：基数排序就闪亮登场啦~。 她一般会在以下场景使用： 1. 神题：WC[2017]挑战 …

为什么要学左偏树 有时候，某些题目要求我们合并两个堆。 合并两个堆，大家都知道可以用splay暴力启发式合并处理。很不幸的是，这玩意的复杂度是$O(nlog^2n)$的，在一些毒瘤题目专门考可并堆的题目中，是注定要被卡的。 可并堆系列算法可以很优雅的解决这系列的算法，她们可以在$O(nlogn)$的时间内处理两个堆合并的问题。而我现在要讲的左偏树就是可并堆中的一种。 什么是左偏树 正如她字面意思一样，是一颗向左“偏”的树。什么叫“向左偏”呢？我们知道，平衡树的时间复杂度比二叉查找树优秀，是因为平衡树的左右子树深度尽…

蒟蒻尚在学习，请各位dalao不要相信本文的任何一个字，包括标点符号。 什么是狄利克雷卷积 狄利克雷卷积定义式如下： $\large f*g(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$ 也可以写作： $\large f*g(n)=\sum_{i*j=n}f(i)*g(j)$ 怎么算狄利克雷卷积 单独计算$f*g(n)$ 显然我们可以根据定义式暴力计算，枚举$i$即可，复杂度$O(\sqrt{n})$ 这里就不上代码了，跟暴力枚举质数长得基本上一…

什么是FFT FFT是用来快速计算两个多项式相乘的一种算法。 如果我们暴力计算两个多项式相乘，复杂度必然是$O(n^2)$的，而FFT可以将复杂度降至$O(nlogn)$ 如何FFT 要学习FFT,我们得先了解它的思想。 首先，我们得先了解如何表示一个多项式。显然，我们最传统的方法表示多项式就是表示它的系数就好。但是，如果我们用系数来计算两个多项式相乘，复杂度无论如何都是$O(n^2)$的。因此，我们引入点值表示法。 补充资料：什么是点值表示 设A(x)是一个n−1次多项式，那么把n个不同的x代入，会得到n个y。这…

本菜鸡尚未学会第二类斯特林数，请各位dalao不要相信本文的任何一个字 什么是第二类斯特林数 在组合数学，Stirling数可指两类数，第一类Stirling数和第二类Stirling数，都是由18世纪数学家James Stirling提出的。 Stirling数有两种，第一类和第二类Stirling数，它们自18世纪以来一直吸引许多数学家的兴趣，如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根（Copenhagen）大学的尼尔森（Niels Nielsen，1865-1931）提出了"Stirlingschen Z…

题面 传送门：POJ Solution 就是裸的扩展中国剩余定理嘛qwq 注意几点：一定要时时刻刻去膜取模，否则一定会爆long long，尤其是算出来的$k_0$ 这里给出几组易锅数据：(第三组容易爆long long) input: 4 18373 16147 8614 14948 8440 17480 22751 21618 6 19576 8109 18992 24177 9667 17726 16743 19533 16358 12524 8280 22731 4 9397 38490 22001 250…

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