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。

相关:算法竞赛数学套路、算法竞赛个人易错点、经典Trick、算法竞赛整理索引。

算法竞赛模板增补
https://sanzenin.top/posts/obsidian/算法竞赛模板增补/
作者
Sanzenin 凪
发布于
2026-10-25
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取