3521 字
18 分钟
算法竞赛模板增补
算法竞赛模板增补
[!tip] 直接使用 下方第一份代码是完整自包含头文件,GNU C++17、无需第三方库;第二份是完整调用示例。提交单文件时,将第一份放到 main 前,再去掉第二份中的本地 include。不要只复制函数调用而遗漏依赖。
本页提供与题面无关的自包含接口。先从下表确认模型、数据范围与复杂度,再复制对应代码。
模板选用与前提
| 接口 | 用于什么 | 时间 / 空间 | 必须满足 |
|---|---|---|---|
| floor_div / ceil_div / to_string128 | 带符号数学整除与128位输出 | O(1) / O(1),输出按位数 | 整除参数64位,除数非0;返回128位 |
| norm / pow_mod / inv_mod | 模归一化、模幂、一般模数逆元 | 幂O(log e),逆元O(log m) | 模数正;逆元m>=2且互质,否则nullopt |
| Comb |
阶乘组合数 | 预处理O(N),查询O(1) / O(N) | MOD为素数、0<=N<MOD,n不超过预处理 |
| floor_sum_nonnegative | 线性分子整除和 | O(log m) / O(1) | n,a,b>=0,m>0,精确答案可放有符号128位 |
| sos(f,super,inverse) | 子集/超集zeta及逆变换 | O(B2^B) / 原地 | 长度是非零2次幂;不是模运算,中间和可放64位 |
| subset_witness | 为每个mask找一个输入子掩码 | O(B2^B+n) / O(2^B) | 0<=B<=24,值在[0,2^B) |
| count_and_zero | 非空下标子集AND为0计数 | O(n+B2^B) / O(n+2^B) | 0<=B<=24,计数取模;相同值下标可分别选 |
| exact_gcd_pairs | i<j的GCD恰好值频数 | O(n+V log V) / O(V) | a_i>0,V=max(a)可开数组,n为int规模 |
| count_subarray_gcd | 所有连续区间GCD为target | 每轮O(log V)个状态,各调用gcd / O(log V) | 非负64位输入;0额外占一个状态,空输入返回0 |
| z_function | 字符串每个后缀与原串的LCP | O(n) / O(n) | 0-based,z[0]=n;空串返回空 |
| tree_path_xor_edges | 批量路径对每条边覆盖奇偶 | O(n+q) / O(n) | 连通树,顶点0-based;结果按输入边顺序 |
| Fenwick2DMax | x<=X且y<=Y的历史点最大值 | 单次O(log² n) / O(n log n) | 预先收集所有更新坐标;仅chmax,不支持删点/降值 |
| convolution / ntt | 998244353模数多项式乘法 | O(L log L) / O(L) | L为>=长度和-1的2次幂,L<=2^23;直接ntt的输入需先归一化 |
| offline_cache_misses | 单项访问序列的最少缓存缺失 | O(n log n) / O(n) | 容量非负、初始空、等载入代价;不适用整批共存模型 |
| clipped_cost_min | 非负参数截断区间代价最小值 | O(n log n) / O(n) | 精确模型见数学套路;x,y>=0,0<=l<=r,128位不溢出 |
固定约定与内存
- SOS数组长度是
1<<B,位外层;子集默认super=false,超集传true。逆变换传第三个参数true。 subset_witness无解返回-1;存在值0时不能把0当无解。inv_mod可能无解,先判断optional;组合数模板不自动检查MOD是否为素数。Fenwick2DMax::NEG=-(1LL<<60),插入值必须大于NEG,查询无点返回NEG;不要直接拿NEG加代价。- NTT模数固定,不能随意改常量。循环卷积需再按目标周期折叠。
- 有符号128位也有上界,不是任意精度整数。乘法前先提升操作数。
- B=22:int数组约16 MiB,long long数组约32 MiB;B=24时分别约64/128 MiB。先估峰值再选B。
- 所有assert表示使用前提,不能代替审题;关闭assert后也必须满足前提。
完整头文件
本地同源文件:cp_ready.hpp。下面内容与文件逐字一致。
#pragma once#include <bits/stdc++.h>
// GNU C++17. All public indices below are zero-based unless stated otherwise.namespace cp {using i64 = long long;using i128 = __int128_t;
// Inputs are signed 64-bit; output is widened (LLONG_MIN / -1 is supported).inline i128 floor_div(i64 a, i64 b) { assert(b != 0); i128 x = a, y = b, q = x / y, r = x % y; return q - (r != 0 && ((r < 0) != (y < 0)));}inline i128 ceil_div(i64 a, i64 b) { assert(b != 0); i128 x = a, y = b, q = x / y, r = x % y; return q + (r != 0 && ((r < 0) == (y < 0)));}inline std::string to_string128(i128 x) { bool neg = x < 0; __uint128_t y = neg ? __uint128_t(-(x + 1)) + 1 : __uint128_t(x); std::string s; do { s.push_back(char('0' + y % 10)); y /= 10; } while (y); if (neg) s.push_back('-'); std::reverse(s.begin(), s.end()); return s;}inline i64 norm(i64 a, i64 m) { assert(m > 0); a %= m; return a < 0 ? a + m : a;}inline i64 pow_mod(i64 a, i64 e, i64 m) { assert(e >= 0 && m > 0); a = norm(a, m); i64 r = 1 % m; while (e) { if (e & 1) r = i128(r) * a % m; a = i128(a) * a % m; e >>= 1; } return r;}// m >= 2; works for composite moduli too. nullopt means gcd(a,m) != 1.inline std::optional<i64> inv_mod(i64 a, i64 m) { assert(m >= 2); i128 r0 = norm(a, m), r1 = m, s0 = 1, s1 = 0; while (r1) { i128 q = r0 / r1; i128 nr = r0 - q * r1, ns = s0 - q * s1; r0 = r1; r1 = nr; s0 = s1; s1 = ns; } if (r0 != 1) return std::nullopt; s0 %= m; if (s0 < 0) s0 += m; return i64(s0);}
// Prime modulus ONLY; 0 <= prepared N < MOD. No Lucas in this class.template<int MOD = 998244353> struct Comb { std::vector<i64> fac, ifac; explicit Comb(int n) : fac(n + 1, 1), ifac(n + 1, 1) { assert(0 <= n && n < MOD); for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD; ifac[n] = pow_mod(fac[n], MOD - 2, MOD); for (int i = n; i; --i) ifac[i - 1] = ifac[i] * i % MOD; } i64 C(int n, int k) const { if (n < 0 || k < 0 || k > n) return 0; assert(n < int(fac.size())); return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD; }};
// Sum_{i=0}^{n-1} floor((a*i+b)/m). Nonnegative signed-64 inputs, m > 0.// The exact answer MUST fit signed __int128. Time O(log m).inline i128 floor_sum_nonnegative(i64 nn, i64 mm, i64 aa, i64 bb) { assert(nn >= 0 && mm > 0 && aa >= 0 && bb >= 0); i128 n = nn, m = mm, a = aa, b = bb, ans = 0; while (true) { if (a >= m) { ans += (n * (n - 1) / 2) * (a / m); a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } i128 y = a * n + b; if (y < m) break; n = y / m; b = y % m; std::swap(a, m); } return ans;}
// f.size() must be a nonzero power of two, with size <= INT_MAX.// All intermediate sums/differences MUST fit i64; these are not modular sums.inline void sos(std::vector<i64>& f, bool super = false, bool inverse = false) { int n = int(f.size()); assert(n > 0 && (n & (n - 1)) == 0); for (int bit = 1; bit < n; bit <<= 1) for (int mask = 0; mask < n; ++mask) if (bool(mask & bit) != super) { if (inverse) f[mask] -= f[mask ^ bit]; else f[mask] += f[mask ^ bit]; }}// Return one input submask for each mask, -1 if absent. 0 <= B <= 24.inline std::vector<int> subset_witness(const std::vector<int>& a, int B) { assert(0 <= B && B <= 24); int n = 1 << B; std::vector<int> f(n, -1); for (int x : a) { assert(0 <= x && x < n); f[x] = x; } for (int bit = 1; bit < n; bit <<= 1) for (int mask = 0; mask < n; ++mask) if (mask & bit) f[mask] = std::max(f[mask], f[mask ^ bit]); return f;}// Count NONEMPTY index-subsets with bitwise AND == 0, modulo MOD.// Equal values at different input indices are distinct choices. 0 <= B <= 24.template<int MOD = 1000000007>int count_and_zero(const std::vector<int>& a, int B) { static_assert(MOD >= 2); assert(0 <= B && B <= 24); int n = 1 << B; std::vector<i64> cnt(n); for (int x : a) { assert(0 <= x && x < n); ++cnt[x]; } sos(cnt, true); std::vector<int> pow2(a.size() + 1, 1); for (size_t i = 1; i < pow2.size(); ++i) pow2[i] = 2LL * pow2[i - 1] % MOD; i64 ans = 0; for (int mask = 0; mask < n; ++mask) { i64 ways = (pow2[cnt[mask]] + i64(MOD) - 1) % MOD; ans += (__builtin_popcount(unsigned(mask)) & 1) ? -ways : ways; ans %= MOD; } return int((ans + MOD) % MOD);}
// Positive a[i] <= V; pairs of indices i < j. Empty input returns {0}.inline std::vector<i64> exact_gcd_pairs(const std::vector<int>& a) { if (a.empty()) return {0}; int V = *std::max_element(a.begin(), a.end()); assert(V >= 1); std::vector<i64> cnt(V + 1), exact(V + 1); for (int x : a) { assert(x > 0); ++cnt[x]; } for (int d = V; d >= 1; --d) { i64 c = 0; for (int k = d; k <= V; k += d) c += cnt[k]; exact[d] = c * (c - 1) / 2; for (int k = d + d; k <= V; k += d) exact[d] -= exact[k]; } return exact;}// Nonnegative a[i]; all zeros are supported. Answer fits i64 for int-sized n.inline i64 count_subarray_gcd(const std::vector<i64>& a, i64 target) { assert(target >= 0); std::vector<std::pair<i64, i64>> cur, nxt; i64 ans = 0; for (i64 x : a) { assert(x >= 0); nxt.clear(); nxt.push_back({x, 1}); for (auto [g, c] : cur) { i64 ng = std::gcd(g, x); if (nxt.back().first == ng) nxt.back().second += c; else nxt.push_back({ng, c}); } cur.swap(nxt); for (auto [g, c] : cur) if (g == target) ans += c; } return ans;}
// z[0] = n. For i > 0, z[i] = LCP(s, s.substr(i)); half-open [l,r).inline std::vector<int> z_function(const std::string& s) { int n = int(s.size()); std::vector<int> z(n); if (n) z[0] = n; for (int i = 1, l = 0, r = 0; i < n; ++i) { if (i < r) z[i] = std::min(r - i, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] > r) { l = i; r = i + z[i]; } } return z;}
// Connected tree, n>=1, zero-based vertices. Edge answers follow input order.// Each (u,v) path toggles all its edges; no LCA is needed for XOR parity.inline std::vector<int> tree_path_xor_edges( int n, const std::vector<std::pair<int,int>>& edges, const std::vector<std::pair<int,int>>& paths) { assert(n >= 1 && int(edges.size()) == n - 1); std::vector<std::vector<std::pair<int,int>>> adj(n); for (int i = 0; i < n - 1; ++i) { auto [u,v] = edges[i]; assert(0 <= u && u < n && 0 <= v && v < n); adj[u].push_back({v,i}); adj[v].push_back({u,i}); } std::vector<int> parent(n, -2), pe(n, -1), order{0}, d(n), ans(n - 1); parent[0] = -1; for (size_t i = 0; i < order.size(); ++i) { int u = order[i]; for (auto [v,e] : adj[u]) if (parent[v] == -2) { parent[v] = u; pe[v] = e; order.push_back(v); } } assert(int(order.size()) == n); for (auto [u,v] : paths) { assert(0 <= u && u < n && 0 <= v && v < n); d[u] ^= 1; d[v] ^= 1; } for (int i = n - 1; i > 0; --i) { int u = order[i]; ans[pe[u]] = d[u]; d[parent[u]] ^= d[u]; } return ans;}
// All potential update coordinates must be supplied at construction.// Incremental point chmax; query max over x<=X AND y<=Y, including ties.// Updates never delete or decrease values. O(log^2 n) per operation.struct Fenwick2DMax { static constexpr i64 NEG = -(1LL << 60); std::vector<i64> xs; std::vector<std::vector<i64>> ys, bit; explicit Fenwick2DMax(const std::vector<std::pair<i64,i64>>& points) { for (auto [x,y] : points) xs.push_back(x); std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); int n = int(xs.size()); ys.resize(n + 1); bit.resize(n + 1); for (auto [x,y] : points) { int p = int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1; for (int i = p; i <= n; i += i & -i) ys[i].push_back(y); } for (int i = 1; i <= n; ++i) { auto& v = ys[i]; std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); bit[i].assign(v.size() + 1, NEG); } } void update(i64 x, i64 y, i64 value) { assert(value > NEG); int p = int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin()); assert(p < int(xs.size()) && xs[p] == x); for (int i = p + 1; i <= int(xs.size()); i += i & -i) { int j = int(std::lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin()); assert(j < int(ys[i].size()) && ys[i][j] == y); for (++j; j < int(bit[i].size()); j += j & -j) bit[i][j] = std::max(bit[i][j], value); } } i64 query(i64 X, i64 Y) const { i64 ans = NEG; int p = int(std::upper_bound(xs.begin(), xs.end(), X) - xs.begin()); for (int i = p; i; i -= i & -i) { int j = int(std::upper_bound(ys[i].begin(), ys[i].end(), Y) - ys[i].begin()); for (; j; j -= j & -j) ans = std::max(ans, bit[i][j]); } return ans; }};
// NTT specifically for 998244353, primitive root 3. No external ACL needed.inline void ntt(std::vector<int>& a, bool inverse) { constexpr int P = 998244353; int n = int(a.size()); assert(n >= 1 && n <= (1 << 23) && (n & (n - 1)) == 0); for (int i = 1, j = 0; i < n; ++i) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit; if (i < j) std::swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { i64 wlen = pow_mod(3, (P - 1) / len, P); if (inverse) wlen = pow_mod(wlen, P - 2, P); for (int l = 0; l < n; l += len) { i64 w = 1; for (int j = 0; j < len / 2; ++j) { int u = a[l + j], v = a[l + j + len / 2] * w % P; a[l + j] = u + v < P ? u + v : u + v - P; a[l + j + len / 2] = u - v >= 0 ? u - v : u - v + P; w = w * wlen % P; } } } if (inverse) { i64 inv = pow_mod(n, P - 2, P); for (int& x : a) x = x * inv % P; }}inline std::vector<int> convolution(std::vector<int> a, std::vector<int> b) { constexpr int P = 998244353; if (a.empty() || b.empty()) return {}; size_t need = a.size() + b.size() - 1; assert(need <= (1 << 23)); int n = 1; while (size_t(n) < need) n <<= 1; for (int& x : a) x = int(norm(x, P)); for (int& x : b) x = int(norm(x, P)); a.resize(n); b.resize(n); ntt(a, false); ntt(b, false); for (int i = 0; i < n; ++i) a[i] = i64(a[i]) * b[i] % P; ntt(a, true); a.resize(need); return a;}
// Standard SINGLE-item cache requests. Initially empty; any int item IDs.// A cache miss loads this item; after each access <= capacity items may remain.// Lazy heap: O(n log n) time / O(n) space, NOT O(n log capacity).inline i64 offline_cache_misses(const std::vector<int>& seq, int capacity) { assert(capacity >= 0); int n = int(seq.size()); if (!capacity) return n; std::vector<int> next(n, n); std::unordered_map<int, int> last, in; for (int i = n - 1; i >= 0; --i) { auto it = last.find(seq[i]); if (it != last.end()) next[i] = it->second; last[seq[i]] = i; } std::priority_queue<std::pair<int, int>> q; i64 misses = 0; for (int i = 0; i < n; ++i) { if (!in.count(seq[i])) { ++misses; if (int(in.size()) == capacity) { while (!q.empty()) { auto [pos, x] = q.top(); q.pop(); auto it = in.find(x); if (it != in.end() && it->second == pos) { in.erase(it); break; } } } } in[seq[i]] = next[i]; q.push({next[i], seq[i]}); } return misses;}
// Minimize F(t)=x*t+y*sum(max(0,r_i-max(l_i,t))) for integer t>=0.// x,y>=0 and 0<=l_i<=r_i, all i64. Returns {minimum, one minimizer}.// Maximum intermediate absolute value must fit signed __int128.inline std::pair<i128, i64> clipped_cost_min( i64 x, i64 y, const std::vector<std::pair<i64, i64>>& intervals) { assert(x >= 0 && y >= 0); std::vector<std::pair<i64, int>> ev; i128 value = 0; for (auto [l, r] : intervals) { assert(0 <= l && l <= r); value += i128(y) * (i128(r) - l); if (l < r) { ev.push_back({l, 1}); ev.push_back({r, -1}); } } std::sort(ev.begin(), ev.end()); i128 best = value; i64 arg = 0, prev = 0, active = 0; for (size_t i = 0; i < ev.size();) { i64 pos = ev[i].first; value += (i128(pos) - prev) * (i128(x) - i128(y) * active); if (value < best) { best = value; arg = pos; } while (i < ev.size() && ev[i].first == pos) active += ev[i++].second; prev = pos; } return {best, arg};}} // namespace cp完整调用示例
本地编译:g++ -std=c++17 -O2 ready/example.cpp -o /tmp/cp-example,在 /home/sanzenin/algo_templates 运行。
#include "cp_ready.hpp"using namespace std;
int main() { cout << cp::to_string128(cp::floor_div(-3, 2)) << '\n'; // -2 cp::Comb<> C(100); cout << C.C(5, 2) << '\n'; // 10 cout << cp::count_and_zero(vector<int>{1, 2, 3}, 2) << '\n'; // 2 cout << cp::count_subarray_gcd({2, 4, 6}, 2) << '\n'; // 4 auto poly = cp::convolution({1, 2}, {3, 4}); for (int x : poly) cout << x << ' '; // 3 10 8 cout << '\n'; cout << cp::offline_cache_misses({1, 2, 3, 1, 2, 3}, 2) << '\n'; // 4 auto parity = cp::tree_path_xor_edges(3, {{0, 1}, {1, 2}}, {{0, 2}, {1, 2}}); for (int x : parity) cout << x << ' '; // 1 0 cout << '\n';
// Model: maximize total length of disjoint RGB-balanced segments, gaps allowed. string s = "RGB"; vector<pair<long long,long long>> prefix{{0,0}}; for (char c : s) { auto [x,y] = prefix.back(); if (c == 'R') ++x, ++y; if (c == 'G') --x; if (c == 'B') --y; prefix.push_back({x,y}); } cp::Fenwick2DMax ft(prefix); ft.update(0, 0, 0); long long dp = 0; for (int i = 1; i <= int(s.size()); ++i) { auto [x,y] = prefix[i]; auto best = ft.query(x,y); // BEFORE insertion: j < i if (best != cp::Fenwick2DMax::NEG) dp = max(dp, i + best); ft.update(x,y,dp-i); } cout << dp << '\n'; // 3}预期逐行输出:-2、10、2、4、3 10 8、4、1 0、3(行末空格无影响)。RGB示例的目标是选不交合法段的最大总长度,允许跳过位置;其他目标需改DP,不能只套数据结构。
复制依赖表
Comb依赖pow_mod,后者依赖norm和i64/i128别名。count_and_zero依赖sos;convolution依赖ntt、pow_mod、norm。- 其余函数依赖公共头文件和类型别名。省事时直接复制整个namespace cp。
分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 22 天
部分内容可能已过时