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

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

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

什么是基数排序 基数排序是一个时间复杂度为：$O(n*MAXNUM/base)$，空间复杂度为$O(base+n)$的优秀排序算法。 基数排序有什么用 我们知道，桶排序可以在$O(MAXNUM)$的时间内，$O(MAXNUM)$的空间内排序一个数组，快速排序可以在$O(nlogn)$的时间内，$O(n)$的空间内排序一个数组。 如果有一个排序任务的最大数字比桶大，而数字数量又爆多怎么办？这时...

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

蒟蒻尚在学习，请各位dalao不要相信本文的任何一个字，包括标点符号。 什么是狄利克雷卷积 狄利克雷卷积定义式如下： $f\cdot g(n)=\sum_{dn}f(d)\cdot g(\frac{n}{d})$ 也可以写作： $f\cdot g(n)=\sum_{i\cdot j=n}f(i)\cdot g(j)$ 怎么算狄利克雷卷积 单独计算$f*g(n)$ 显然我们可以根据定义式...

什么是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$两两互质 . 如果不互质怎么办？当然是把出题者拖出去吊起来打啊。...