多项式线性凸包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 - ...
数据结构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& ...
数据结构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) ...
杂项单测多测1234567891011121314151617181920212223242526272829303132333435#include <bits/stdc++.h>#define ranges std::ranges#define views std::viewsusing u32 = unsigned;using i64 = long long;using u64 = unsigned long long;using pii = std::pair<int, int>;using a3 = std::array<int, 3>;using a4 = std::array<int, 4>;const int N = 1e6;const int MAXN = 1e6 + 10;const int inf = 1e9;// const int mod = 1e9 + 7;const int mod = 998244353;std::mt19937_64 rng(std::chrono::steady_clock::now() ...
数论常见数列调和级数满足调和级数 ，可以用 来拟合，但是会略小，误差量级在 左右。本地可以在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
除此之外，对于任意两个相邻的素 ...
树上问题树的直径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 ...
线性代数线性基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 ...
算法竞赛
未读数论&组合数学常见结论及例题球盒模型（八种）参考链接。给定 个小球 个盒子。
球同，盒不同、不能空
隔板法： 个小球即一共 个空，分成 堆即 个隔板，答案为 。
球同，盒不同、能空
隔板法：多出 个虚空球，答案为 。
球同，盒同、能空
的 项的系数。动态规划，答案为
$$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]; } }}
球同，盒同、不能空
...
组合数学组合数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] ...
