常用例题逆序对（归并排序解）
性质：交换序列的任意两元素，序列的逆序数的奇偶性必定发生改变。
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 - ...
图论常见概念
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} ，即偏心距最小的点。如下图，图的中心即为 点。
图的绝对中心：可以定义在边上的图的中心。
图的半径：图的半径不同于圆的半径，其不等于直径的一半（但对于绝对中心定义上的直径 ...
数据结构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) ...
数据结构A笛卡尔树小根笛卡尔树
12345678910111213cin >> n;for (int i = 0;i < n;++i)cin >> nums[i];for (int i = 0;i < n;++i)rs[i] = -1;for (int i = 0;i < n;++i)ls[i] = -1;top = 0;for (int i = 0; i < n; i++) { int k = top; while (k > 0 && nums[stk[k - 1]] > nums[i]) k--; if (k) rs[stk[k - 1]] = i; // rs代表笛卡尔树每个节点的右儿子 if (k < top) ls[i] = stk[k]; // ls代表笛卡尔树每个节点的左儿子 stk[k++] = i; top = k;}
dsu并查集路径优化(普遍)123456789101112struct dsu { std::vector<int& ...
数论常见数列调和级数满足调和级数 ，可以用 来拟合，但是会略小，误差量级在 左右。本地可以在500ms内完成 量级的预处理计算。
N的量级
1
2
3
4
5
6
7
8
9
累加和
27
482
7’069
93‘668
1’166‘750
13‘970’034
162‘725’364
1‘857’511‘568
20’877‘697’634
下方示例为求解 到 中各个数字的因数值。
1234567const int N = 1E5;vector<vector<int>> dic(N + 1);for (int i = 1; i <= N; i++) { for (int j = i; j <= N; j += i) { dic[j].push_back(i); }}
素数密度与分布
N的量级
1
2
3
4
5
6
7
8
9
素数数量
4
25
168
1‘229
9’592
78‘498
664’579
5‘761’455
50‘847’534
除此之外，对于任意两个相邻的素 ...
线性代数线性基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 ...
杂项整数域除法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 ...
算法竞赛
未读数论&组合数学常见结论及例题球盒模型（八种）参考链接。给定 个小球 个盒子。
球同，盒不同、不能空
隔板法： 个小球即一共 个空，分成 堆即 个隔板，答案为 。
球同，盒不同、能空
隔板法：多出 个虚空球，答案为 。
球同，盒同、能空
的 项的系数。动态规划，答案为
$$dp[i][j]=\left{\right.$$
12345678910int dp[15][15];void choose(int n) { for(int i = 0; i < n; i ++) { for(int j = 1; j < n; j ++) { if(i <= 1 || j == 1) dp[i][j] = 1; else if (i < j) dp[i][j] = dp[i][j - 1]; else dp[i][j] = dp[i][j - 1] + dp[i - j][j]; } }}
球同，盒同、不能空
...
树上问题树的直径123456789101112131415161718192021222324252627282930313233struct Tree { int n; vector<vector<int>> ver; Tree(int n) { this->n = n; ver.resize(n + 1); } void add(int x, int y) { ver[x].push_back(y); ver[y].push_back(x); } int getlen(int root) { // 获取x所在树的直径 map<int, int> dep; // map用于优化输入为森林时的深度计算，亦可用vector function<void(int, int)> dfs = [&](int x, int fa) -> void { for (auto y : ver ...
组合数学组合数debug提供一组测试数据： 377’389’666’165’540’953’244’592’352’291’892’721’700，模数为 时为 ； 时为 。
逆元+卢卡斯定理（质数取模） ，模数必须为质数。
1234567891011121314151617181920212223242526272829303132333435363738struct Comb { int n; vector<Z> _fac, _inv; Comb() : _fac{1}, _inv{0} {} Comb(int n) : Comb() { init(n); } void init(int m) { if (m <= n) return; _fac.resize(m + 1); _inv.resize(m + 1); for (int i = n + 1; i <= m; i++) { _fac[i] = _fac[i - 1] ...
