你好，我是 zbl2012 👋

质数筛也是数论中非常重要的一个部分。 根号筛 这个是很多人第一个学的筛法，也是最简单的筛法。 做法很简单，就是枚举 2 到 n-1 里所有的数，如果当前数可以被 n 整除，那么 n 显然就是一个和数。直到跑完循环也没返回，就说明 n 是一个指数。当然，n<2 要特判，n=2 也要特判。这样做每次判断一个数的时间复杂度是 On，判断 n 个数的时间复杂度是 On^2。太慢了，要优化。 ...

从 1,2,3,...,n 中选择 m 个数的方案数，记为 \dbinom{n}{m}，也可记为 C^mn。读作 “n 取 m”。\dbinom{n}{m}=\frac{n!}{m!n-m!} On^2 引理：在杨辉三角中的第 n 行 m 列等于 \dbinom{n}{m}。 根据这个引理，我们可以用构造杨辉三角的形式构造组合数。 杨辉三角的构造很简单，就是当前位等于上面的加左上的，也就...

逆元的诞生是源于除法没有同余定理。 逆元的定义：在模意义下，一个数 a 除以 b，等于乘 b 的逆元。 首先我们要知道什么是同余定理。其实就是针对取模的运算的基本原理： 当 a\equiv b\pmod m,c\equiv d\pmod m,m>0 时： a+c\equiv b+d\pmod m\\a-c\equiv b-d\pmod m\\ac\equiv bd\pmod m ...

快速幂是很多数学题的最基本的东西，是一种可以在 O\log n 的复杂度求解 a^n 的问题的算法。 一般来说，求解 a^n 的问题要循环 n 次，每次乘 a，时间复杂度 On。 但是快速幂用到了一个性质：任何一个正整数都可以写成几个 2 的次幂的和，其实就是可以转换成二进制。 所以可以将 a^n 转换成： n=2^{x1}+2^{x2}+2^{x3}+...+2^{xt},t\le\...

树的直径就是树上两点的最远距离。 如果暴力 dfs 会发现，最后情况下每一次都把树跑满，时间复杂度 On^2，显然是不可以通过 10^5 的数据的。 考虑优化成 On。 假设有一点 x，通过一次 On 的 dfs 找到了自己的最远的是 y，此时发现，如果再跑一次以 y 为起点的 dfs，这个 dfs 中的跑的距离就是答案了。 注意点 1.实现时 dfs 中的边界。 cod...

树的重心就是在一个树里，删去一个节点，使剩下的最大联通快最小。 我们要在 On 的时间内，求出这个重心。 如果每一个节点当根，每一个都跑一遍 dfs 的话，时间复杂度是 On^2，显然不可以通过。 所以就要用到一个技巧：换根。 首先，我们要用 dfs 求出以 1 为根的每个节点的子树大小和父节点。然后就是换根环节了，随便观察一个树以 1 为根时的每个节点的子树大小，会发现：当换成 ...

Kruskal Kruskal 求最小生成树是一种以边贪心的最小生成树算法。 设一张图的点数为 n，边数为 m。 观察一个图和它的最小生成树，发现在构造最小生成树的过程中，每一次是选择一条较小的边去连通，所以考虑贪心。 首先肯定是按边权从小到大排序，然后跑每一条边。如果这个边得起点和重点没有放进最小生成树的集中，就把他们放进集合，并将答案加入边权，总边数 +1。如果在跑的过程中，总边...

学了AC自动机的拓扑排序优化，故来补一下。 拓扑排序是一种在DAG有向无环图上求解关于先后顺序的算法。其中它排序出来的结果叫做拓扑序。 拓扑排序其实可以抽象化成家谱：给定每个人的子辈，求所有人的辈分排序。 拓扑排序本质上就是一个 bfs。 首先遍历所有点，把入度为 0 的点找出来，不难证明，这些点就是最高辈分的那些点，因为他们都没有父节点。把这些点入队，然后跑 bfs，将队头的...

背包DP是 DP 中最基础的一种，比较好理解的，接下来介绍几种背包DP。 首先要了解背包DP解决的问题，就是类似于求给定一个可取价值和一些物品数量和单个价值，在各种约束下可以达到的最值。 01背包 属于最基础的了，但是其他背包基本都要建立在它身上。 01背包就是有 n 物品，每个物品有它的价值 vi 和重量 wi，你可以选总容量为 W 的物品，但是每件物品只能选一件，求最大价值。...