基础算法常用函数12345678910111213141516int mypow(int n, int k, int p = MOD) { // 复杂度是 log N int r = 1; for (; k; k >>= 1, n = n * n % p) { if (k & 1) r = r * n % p; } return r;}i64 mysqrt(i64 n) { // 针对 sqrt 无法精确计算 ll 型 i64 ans = sqrt(n); while ((ans + 1) * (ans + 1) <= n) ans++; while (ans * ans > n) ans--; return ans;}int mylcm(int x, int y) { return x / gcd(x, y) * y;}
12345678910111213141516171819202122template<class T> int log2floor(T n) { // ...
图论常见结论及例题常见结论
要在有向图上求一个最大点集，使得任意两个点 之间至少存在一条路径（可以是从 到 ，也可以反过来，这两种有一个就行），即求解最长路；
要求出连通图上的任意一棵生成树，只需要跑一遍 bfs ；
给出一棵树，要求添加尽可能多的边，使得其是二分图：对树进行二分染色，显然，相同颜色的点之间连边不会破坏二分图的性质，故可添加的最多的边数即为 ；
当一棵树可以被黑白染色时，所有染黑节点的度之和等于所有染白节点的度之和；
在竞赛图中，入度小的点，必定能到达出度小（入度大）的点 See 。
在竞赛图中，将所有点按入度从小到大排序，随后依次遍历，若对于某一点 满足前 个点的入度之和恰好等于 ，那么对于上一次满足这一条件的点 ， 到 点构成一个新的强连通分量 See 。
举例说明，设满足上方条件的点为 ，那么点 到 构成一个强连通分量、点 到 构成一个强连通分量。
选择图中最少数量的边删除，使得图不连通，即求最小割；如果是删除点，那么拆点后求最小割 See。
如果一张图是平面图，那么其边数一定小于等于 See 。
若一张有向完全图存在环，则一定存 ...
多项式线性凸包123456789101112131415161718192021222324252627282930struct Line { i64 a, b, r; bool operator<(Line l) { return pair(a, b) > pair(l.a, l.b); } bool operator<(i64 x) { return r < x; }};struct Lines : vector<Line> { static constexpr i64 inf = numeric_limits<i64>::max(); Lines(i64 a, i64 b) : vector<Line>{{a, b, inf}} {} Lines(vector<Line>& lines) { if (not ranges::is_sorted(lines, less())) ranges::sort(lines, less()); for (auto [a, b, _] : l ...
常用例题逆序对（归并排序解）
性质：交换序列的任意两元素，序列的逆序数的奇偶性必定发生改变。
12345678910111213141516171819202122LL a[N], tmp[N], n, ans = 0;void mergeSort(LL l, LL r){ if (l >= r) return; LL mid = (l + r) >> 1, i = l, j = mid + 1, cnt = 0; mergeSort(l, mid); mergeSort(mid + 1, r); while (i <= mid || j <= r) if (j > r || (i <= mid && a[i] <= a[j])) tmp[cnt++] = a[i++]; else tmp[cnt++] = a[j++], ans += mid - i + 1; for (LL k = 0; k < r - ...
多边形相关平面多边形两向量构成的平面四边形有向面积123template<class T> T areaEx(Point<T> p1, Point<T> p2, Point<T> p3) { return cross(b, c, a);}
判断四个点能否组成矩形/正方形可以处理浮点数、共点的情况。返回分为三种情况： 代表构成正方形； 代表构成矩形； 代表其他情况。
1234567891011template<class T> int isSquare(vector<Pt> x) { sort(x.begin(), x.end()); if (equal(dis(x[0], x[1]), dis(x[2], x[3])) && sign(dis(x[0], x[1])) && equal(dis(x[0], x[2]), dis(x[1], x[3])) && sign(dis(x[0], x[2])) && ...
动态规划01背包有 件物品和一个容量为 的背包，第 件物品的体积为 ，价值为 ，求解将哪些物品装入背包中使总价值最大。
思路：
当放入一个价值为 的物品后，价值增加了 ，于是我们可以构建一个二维的 数组，装入第 件物品时，背包容量为 能实现的 最大价值，可以得到 转移方程 。
123456for (int i = 1; i <= n; i++) for (int j = 0; j <= W; j++){ dp[i][j] = dp[i - 1][j]; if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); }
我们可以发现，第 个物品的状态是由第 个物品转移过来的，每次的 转移过来后，第 个方程的 已经没用了，于是我们想到可以把二维方程压缩成 一维 的，用以 优化空间复杂度。
123for (int i = 1; i <= n; i++) //当前装第 i 件物品 for (int ...
图论常见概念
oriented graph：有向图
bidirectional edges：双向边
平面图：若能将无向图 画在平面上使得任意两条无重合顶点的边不相交，则称 是平面图。
无向正权图上某一点的偏心距：记为 Missing or unrecognized delimiter for \bigecc(u) = \max \big{ dist(u, v) \big} ，即以这个点为源，到其他点的所有最短路的最大值。如下图 点， 即为 。
图的直径：定义为 Missing or unrecognized delimiter for \bigd = \max \big{ ecc(u) \big} ，即最大的偏心距，亦可以简化为图中最远的一对点的距离。
图的中心：定义为 Missing or unrecognized delimiter for \bigarg=\min \big{ ecc(u)\big} ，即偏心距最小的点。如下图，图的中心即为 点。
图的绝对中心：可以定义在边上的图的中心。
图的半径：图的半径不同于圆的半径，其不等于直径的一半（但对于绝对中心定义上的直径 ...
杂项整数域除法1234567891011121314151617i64 ceilDiv(i64 n, i64 m) { if (n >= 0) { return (n + m - 1) / m; } else { return n / m; }}i64 floorDiv(i64 n, i64 m) { // m > 0 if (n >= 0) { return n / m; } else { return (n - m + 1) / m; }}
from yorisou
12T floor(T x, U y) { return x / y - (x % y and (x ^ y) < 0); }T ceil(T x, U y) { return floor(x + y - 1, y); }
单测多测1234567891011121314151617181920212223242526272829303132333435#include <bits/s ...
数据结构B基于状压的线性 RMQ 算法严格 预处理， 查询。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172template<class T, class Cmp = less<T>> struct RMQ { const Cmp cmp = Cmp(); static constexpr unsigned B = 64; using u64 = unsigned long long; int n; vector<vector<T>> a; vector<T> pre, suf, ini; vector<u64> stk; RMQ() {} RMQ(const vector<T> &v) { init(v) ...
线性代数线性基12345678910111213141516171819202122232425262728std::vector<i64> get_linear_basis(std::vector<i64>& nums, int N = 63) { std::vector<i64> p(N + 1); auto insert = [&](i64 x) { for (int s = N;s >= 0;--s)if (x >> s & 1) { if (!p[s]) { p[s] = x; break; } x ^= p[s]; } }; for (auto& x : nums) insert(x); return p;}signed main() { std::ios::sync_with_stdio(fa ...
