递推 给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cba mod (109+7)C_b^a \bmod (10^9+7)Cba​mod(109+7) 的值。 数据范围 1≤n≤100001\le n \le 100001≤n≤10000 1≤b≤a≤20001\le b \le a \le 20001≤b≤a≤2000 题目链接：AcWing 885。 复杂度：O(n2)O(n^ ...

欧几里得算法 辗转相除法，设 a≥ba\ge ba≥b 原理是： gcd⁡(a,b)=gcd⁡(b,a−b)\gcd(a,b)=\gcd(b,a-b) gcd(a,b)=gcd(b,a−b) 这个原因是 gcd⁡(a,b)∣a,gcd⁡(a,b)∣b\gcd(a,b)\mid a,\gcd(a,b)\mid bgcd(a,b)∣a,gcd(a,b)∣b，所以相减同样满足 gcd⁡(a,b)∣(a− ...

欧拉函数 对于正整数 nnn，欧拉函数 φ(n)\varphi(n)φ(n) 代表小于 nnn 的数中，所有与 nnn 互质的数的个数。一般认为 φ(1)=1\varphi(1) = 1φ(1)=1。 性质1 对于素数 ppp，1∼(p−1)1\sim (p-1)1∼(p−1) 都与其互质，所以 φ(p)=p−1\varphi(p)=p-1φ(p)=p−1。 性质2 对于互质的 m,nm,nm,n ...

判定 所有边都需要连通，其次： 对于无向图 存在欧拉路径的充要条件：度数为奇数的点只能有0或2个。 存在欧拉回路的充要条件：不能有度数为奇数的点。 对于有向图 存在欧拉路径的充要条件：所有点入度等于出度，或者有两个点分别满足 din = dout+1, dout=din+1。 存在欧拉回路的充要条件：所有点入度等于出度。 欧拉回路 给定一张图，请你找出欧拉回路，即在图中找一个环使 ...

倍增 给定一棵包含 n 个节点的有根无向树，节点编号互不相同，但不一定是 1∼n。 有 m 个询问，每个询问给出了一对节点的编号 x 和 y 询问 x 与 y 的祖孙关系。 输入格式 输入第一行包括一个整数 表示节点个数； 接下来 n 行每行一对整数 a 和 b，表示 a 和 b 之间有一条无向边。如果 b 是 −1，那么 a 就是树的根； 第 n+2 行是一个整数 m 表示询问个数； 接下来 ...

简介 原理 利用三角不等式的可以用图论的方式求解一个不等式组，设 δ(s,x)\delta(s,x)δ(s,x) 为 s→xs \to xs→x 的最短路长度，那么： δ(s,x)≤δ(s,y)+w(y,x)\delta(s,x)\le\delta(s,y)+w(y,x) δ(s,x)≤δ(s,y)+w(y,x) 对于下面的不等式组，可以构造一个图来求最短路找到一个可行解。 {x1≤x2+C1x2 ...

SPFA 负环模板 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你判断图中是否存在负权回路。 建立一个虚拟原点，到所有点的距离都是 0，因此需要在初始化时把所有点都加入队列中，并且不用初始化距离。 由于 SPFA 算法只会把找到路径更小的节点加入到队列中，所以根据抽屉原理只要遍历一个节点的路径大于等于所有节点的数量，那么这条路径一定存在环，并且由于是 S ...

单源最短路 道路与航线 农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。 他想把牛奶送到 T 个城镇，编号为 1∼T。 这些城镇之间通过 R 条道路 (编号为 1 到 R) 和 P 条航线 (编号为 1 到 P) 连接。 每条道路 i 或者航线 i 连接城镇 Ai 到 Bi，花费为 Ci。 对于道路，花费 Ci 为正数；然而航线的花费很神奇，花费 Ci 可能是负数。 道路是双向的，可以从 ...

简介 DFS(Deep First Search)是遍历方式的一种，它可以用来求排列组合方式的这种遍历问题，实现起来一般使用递归。 剪枝 剪枝策略： 优化搜索顺序 应该首先搜索分支较少的节点，使得它可以被剪掉尽可能多的节点。 排除等效冗余 如果不考虑顺序，尽量用组合的方式搜索以减少冗余。 可行性剪枝 最优性剪枝 记忆化搜索（DP） N皇后 n 皇后问题是指将 n 个皇后放 ...

简介 A* 算法用来解决状态数量非常庞大的问题，如前面遇到的八数码这种每一步变换都是不确定的这类问题，它与堆优化版的 Dijkstra 算法长得很像。 流程 用小根堆存储所有节点，排序依据是这个节点到原点的距离 + 到终点的估计距离。 从队列中取出第一个节点，如果这是终点就找到了最短距离。 将当前节点的所有没有遍历过或者能缩短现有路径长度的子节点入队。 重复上述流程。 证明 设估计当前点到终点 ...