Skip to content

使用说明

源码、头文件路径和网页分类采用同一套目录：

目录 内容
noya/head.hpp 高频使用的公共入口，保留简短 include
noya/ds/ 数据结构
noya/graph/ 图与树算法
noya/string/ 字符串
noya/math/ 数论、代数、多项式
noya/geometry/ 计算几何
noya/dp/ 动态规划
noya/optimization/ 优化与搜索
noya/utility/ 调试、I/O、随机工具

公共入口为 #include "noya/head.hpp"；按需包含具体算法， 例如 #include "noya/ds/sparse_table.hpp"。网站分类与源码目录对应。

写题与预编译

保留源码开头的 #include "noya/head.hpp"，方便普通编译和展开提交。 Linux/macOS 安装 Python 3 与 GCC/Clang 后，可以从题目目录直接编译：

bash /path/to/libra/compile.sh main.cpp -o main -- -O2
CXX=clang++ bash /path/to/libra/compile.sh main.cpp -o main -- -O2
# 可选：在同一工作目录提前构建同样选项的缓存
bash /path/to/libra/precompile.sh -- -O2
# 使用提交模式编译，关闭默认 local 调试宏
bash /path/to/libra/compile.sh main.cpp -o main --submission -- -O2

第一次自动构建 PCH，之后复用；编译器、选项、模式或依赖变化会选择新的缓存。 缓存位于库内 .cache/pch/，不会在源码旁生成 .gch。 默认选项来自 compile_flags.txt，额外编译选项放在 -- 后面； 配置文件的相对 include 路径基于库目录，命令行相对路径基于当前题目目录。

这个入口会在源码之前载入公共头。影响公共头的宏（例如 local、NDEBUG） 必须通过 -D/-U 设置，不要依赖源码中 include 前的宏定义。 --submission 是本地编译模式，单文件提交仍使用展开器。 普通编译命令不会自动使用这里的独立缓存；使用 compile.sh，或在自己的 CMake 目标上调用 target_precompile_headers。详细缓存说明见仓库 tools/README.md。

Monoid 与 build

build 是正常的重建入口，构造函数使用同一套实现。Monoid 统一提供 value_type、unit()、op(a, b)。op 必须满足结合律，unit() 是双侧单位元； 普通 sparse table 还要求信息可重，也叫幂等性。运算须保持从左到右的顺序， 不要求交换律。

写题时可以这样理解这几个词：

  • 可合并：知道左右两段的信息，就能合并出整段的信息，且分组方式不影响结果 （结合律）。例如区间和、最小值、矩阵乘积。
  • 可重：同一段信息合并两次，答案仍然不变，即 \(\operatorname{op}(x,x)=x\)。 min/max/gcd/按位与/按位或 都可重；求和、异或通常不可重。
  • 静态：建好以后只查询；数组改了，需要重新构建。

因此，sparse_table 就是“可重信息的 \(O(n \log n)\) 预处理、 \(O(1)\) 静态区间查询”。查询拿两段预处理结果覆盖目标区间，中间可能重叠， 但可重信息重复合并不会改变答案。 disjoint_sparse_table 则选互不重叠的两段，只要求信息可合并， 也能做到 \(O(n \log n)\) 预处理、\(O(1)\) 查询。 如果只查区间和或异或，优先用更简单的前缀数组，预处理只需 \(O(n)\)。

#include "noya/ds/sparse_table.hpp"
#include <algorithm>
#include <limits>
#include <vector>

struct minimum {
  using value_type = int;
  static int unit() { return std::numeric_limits<int>::max(); }
  static int op(int a, int b) { return std::min(a, b); }
};

int main() {
  std::vector<int> values{5, 2, 7, 1};
  noya::sparse_table<minimum> table(values);
  int x = table.prod(1, 4); // [1,4)，得到 1
  table.build(std::vector<int>{8, 3});
  int y = table.get(0);    // 8
  table.build(4, [](int i) { return i * i; });
  return x + y == 9 ? 0 : 1;
}

sparse_table、disjoint_sparse_table、segtree、lazy_segtree 共用数组构造、 build(values)、build(n, generator)、get(i)、prod(l,r)、all_prod()、 size()、empty() 约定。默认构造为空；空区间返回 unit()。 lazy_segtree<Monoid, Action> 的 Action 仍需提供映射及复合操作。

场景 类型 构建 区间查询 更新
静态可重信息，如 min/max/gcd sparse_table<Monoid> \(O(n \log n)\) \(O(1)\) 重建
静态可合并信息，不要求可重 disjoint_sparse_table<Monoid> \(O(n \log n)\) \(O(1)\) 重建
单点修改 segtree<Monoid> \(O(n)\) \(O(\log n)\) \(O(\log n)\)
区间映射 lazy_segtree<Monoid, Action> \(O(n)\) \(O(\log n)\) \(O(\log n)\)
队尾加入、队首删除 swag<Monoid> \(O(n)\) 整队 \(O(1)\) 均摊 \(O(1)\)

复杂度按值类型和 op/映射为 \(O(1)\) 计；例如字符串拼接的实际代价取决于字符串长度。 SWAG 使用 push_back、pop_front、all_prod，也支持数组构造、build 和 clear。 旧的 sparse_table<Value, op, identity> 与 swag<Value, op, identity_function> 改为 Monoid 类型接口。

容器拥有自己的值，不保存调用者数组的引用。静态表可用 table.build(std::move(values)) 接管原数组存储，调用后不要依赖原数组内容。 线段树的生成器版本直接填充叶子，不构造中间数组。静态表重建复用各层容量并按下标写入； Monoid 和树查询均在编译期分派，没有虚函数或 std::function 调用。

二元布尔约束

two_sat(n) 的变量编号为 \([0,n)\)；add_clause(a,x,b,y) 表示 （变量 \(a\) 的值为 \(x\)）或（变量 \(b\) 的值为 \(y\)）。可继续加约束并多次 solve()， 每次从当前完整公式重新求解，返回独立的 optional<vector<bool>>； 无解为 nullopt，零变量公式返回有值的空数组。不是动态维护可满足性的接口。 要求 \(2n\) 和两倍约束数可用 int 表示；添加约束均摊 \(O(1)\)，求解 \(O(n+C)\)， 空间 \(O(n+C)\)，递归深度最坏 \(O(n)\)。

同变量的恒真式不加边，单文字约束只加一条蕴含边；其余约束加两条边。 Tarjan 的 low-link 保存在递归局部变量中，直接比较逆拓扑分量编号生成赋值， 省去全局 low 数组、分量编号翻转和 SCC 返回数组的额外拷贝。

无向图最短环

undirected_girth(n, edges) 用于无权无向多重图，返回一条最短简单环的边编号， 编号沿环排列、从 0 开始；森林返回空数组，自环长度为 1，平行边可形成长度 2 的环。 输入不变；多个最短环之间不保证固定选择、起点或方向。 要求 \(0\le n<\mathrm{INT\_MAX}\)，端点在 \([0,n)\)，边数不超过 INT_MAX。

先检查自环和重边，再剥去度数不足 2 的顶点；森林在 \(O(n+m)\) 内结束。 对剩余顶点逐个 BFS，并用当前最优长度限制搜索深度；重建时去掉两条树路径的共同前缀， 返回的边不会组成带重复顶点的闭合游走。最坏时间 \(O(n(n+m))\)，空间 \(O(n+m)\)。 这是普通的精确最短环算法，长环等输入仍可能需要二次时间。

树接口分层

根深度统一为 0，根父亲为 -1，子树区间为 \([l,r)\)。

需求 类型 构建 查询 存储
父亲、深度、DFS 序、子树区间 tree_preprocessing \(O(n)\) \(O(1)\) 五个线性数组
高频 LCA 与距离 fastlca \(O(n \log n)\) \(O(1)\) 基础数组与单整数 RMQ 表
路径拆分、向上跳、路径第 \(k\) 点 hld \(O(n)\) \(O(\log n)\) 基础数组、重儿子和链顶

三者共用递归遍历；HLD 不保留邻接表副本，RMQ LCA 不建立额外倍增表。 通用的祖先判断、换根 LCA、路径相交等由编译期分派共用。 is_subtree(a,b) 表示 \(a\) 位于 \(b\) 的子树内，包含 \(a=b\)；DFS 序保留原邻接次序。 path(a,b) 按 \(a\) 到 \(b\) 的方向返回所有顶点，包含两端；按边数预留一个结果数组， 同点直接返回单点路径，复杂度为 \(O(\text{路径顶点数}+\text{LCA 查询耗时})\)。 intersection(a,b,c,e) 的端点沿第二条路径 \(c\) 到 \(e\) 排列；无交集返回 {-1,-1}， 仅交于一点时返回两次该顶点。构建采用递归遍历，路径交仍计算六次 LCA。 build_virtual_tree(tree, vertices) 接受任一查询实现的 const 引用， 复杂度为 \(O(k\log k+k\cdot\text{LCA 查询耗时})\)，不会复制底层树。 关键点可重复，空集合返回四个空数组；不会强制加入原树根。 结果 vs 是按该后端 DFS 序排列的原顶点编号，fa 是父亲在 vs 中的位置， len 是压缩边对应的原树边数（不是权值和），key 标记原关键点。 首点是所有关键点的 LCA，父亲为 -1、长度为 0；两个后端的 DFS 顺序可以不同。 相邻关键点的 LCA 单独排序去重，再与已排序关键点做集合并； 使用已有 fa 向上找最近虚树祖先，省去额外栈，保持各后端的完整输出顺序。

fastlca(graph, root) 根据边类型识别无权/整数权树，不再接收权重开关。 有权根距离和查询结果须能用 int64_t 表示。 跳祖先或查询路径上的第 \(k\) 个点，使用 HLD 的 kth_ancestor、kth_on_path。重建为空树会清除旧状态。

fastlca 保留父节点 DFS 序上的普通稀疏表，每格只存一个整数； 查询先对 DFS 序区间取最小值，再通过 tl 还原顶点。 需要线性空间时可结合上表选择 HLD。

HLD 选重儿子时直接遍历已有 DFS 序，根据父亲和子树大小更新，省去一趟邻接表扫描； 同大小时仍选原邻接次序中最先出现的儿子。 chain(a,b) 仍按 \(a\) 到 \(b\) 的路径顺序返回 (l,r,forward) 半开区间； 用两个数组分别收集两侧区间，反转终点一侧后拼接即可。 LCA、跳点接口和 \(O(n)\) 构建、\(O(\log n)\) 查询界保持不变。

树直径与直径合并

noya/graph/tree_diameter.hpp 的三个接口分别如下，输入顶点编号均为 \([0,n)\)：

接口 返回结果 边权要求
tree_diam(g) (长度, a, b, eccentricity)，最后一项是每个点到最远点的距离 无权树
weighted_tree_diameter(g) (最大路径权值, 路径顶点序列)，允许零条边的路径 可含负权；权值与最大路径和须能由 Weight 表示
diameter_monoid 顶点集合的 (直径长度, 两个端点)，用于线段树等合并 非负树度量；距离须能由 int64_t 表示

两个求直径函数都是 \(O(n)\) 时间、\(O(n)\) 空间，不修改输入。 无权版本从 0 开始做三次 BFS；每次最远点平局都选编号最小的顶点， 返回的数组是离心率，不是路径。空树返回 (-1,-1,-1,{})。 BFS 只保存距离，省掉未使用的前驱数组，并复用已有距离数组存放离心率。

带权版本做一次树形 DP，合并当前点向两个子树延伸的最优路径，再用父亲数组 还原路径。负分支不作为后续的最优向下路径；例如边权为 0–1:-100、 1–2:50、1–3:60 时，答案是路径 2–1–3 的 110，不能使用两次最远点搜索。 空树返回 (0,{})，非空且所有边非正时返回 (0,{0})。 有多个答案时允许返回任意一条，不保证路径方向或平局选择。 递归深度最坏 \(O(n)\)；浮点权值要求有限， 运算存在通常的浮点舍入误差。

diameter_monoid::make(v) 建立单点状态，unit() 表示空集合， op(a,b) 合并两集合。端点按编号升序存储；长度平局选字典序最大的端点对， 这样由 make/op/unit 产生的规范状态满足结合律和交换律。 手写的反向端点会被排序，但不要用任意非规范状态替代集合的规范直径。 一次合并至多查询 4 次距离；重复端点去重后，单点与单点只查询 1 次， 单点与一条直径至多查询 2 次，合并仍为 \(O(1)\) 时间和空间。

先用 diameter_monoid::set_lca(lca) 绑定 fastlca。 这个指针由所有实例共享，重新绑定会影响所有实例；上下文必须一直存活， 参与合并的状态必须来自同一棵树。LCA 的预处理成本另计。 这里依赖非负树度量，不能因为带权路径函数支持负权，就给 monoid 使用负边。

树上距离分布

tree_distance_frequency(g) 接收 \([0,n)\) 上的无权无向树，返回长度为 \(n\) 的 vector<int64_t>：answer[d] 是距离恰为 \(d\) 的不同顶点无序对数量。 因此 answer[0]=0，总和为 \(\frac{n(n-1)}2\)；空树返回空数组，单点返回 {0}。 输入不会被修改，时间 \(O(n \log^{2} n)\)、空间 \(O(n)\)，包括最坏 \(O(n)\) 的递归栈。

每个点分治重心只收集一次深度直方图：整体直方图的平方减去各分支直方图 的平方，留下经过重心的有序点对，最后除以 2。长度不超过 60 的直方图 直接用 64 位整数相乘。更长时调用 ACL 卷积；若直方图总和为 \(S\)、最大项为 \(M\)， 任意平方系数都不超过 \(SM\)。这个上界小于 998244353 时一个模数就能精确 还原，否则使用两个模数和 CRT；没有浮点误差，也不会把模意义计数当整数答案。

\(n < 2^{21}\) 时任意树形都满足当前 NTT 长度和 CRT 范围要求。更大的输入需逐次 满足卷积范围：单模数平方结果长度不超过 \(2^{23}\)；双模数不超过 \(2^{21}\)， 且 \(SM<998244353\cdot924844033\)。小直方图走整数计算，不受 NTT 长度限制。 顶点数须能由 int 表示，输入必须确实是一棵树；边数断言不替代一般图合法性检查。

静态全根路径仿射复合和

tree_path_affine_sums(values,edges,affine) 一次性返回所有终点的答案。 对于每个终点 \(r\)，把每个来源 \(v\) 的点值沿 \(v\)→\(r\) 路径依次应用边函数，再对所有 \(v\) 求和； \(r\) 自己贡献未经变换的 values[r]。令 \(a_i\)、\(b_i\) 分别为 affine[i].first、affine[i].second，第 \(i\) 条无向边在两个方向均使用 \(a_i x+b_i\)，不是互逆映射，离 \(r\) 最近的函数最后应用。 例如链 0—1—2，点值 (10,20,30)、边映射 \((2x+1,3x+4)\)，返回 (240,135,161)。

这是静态的全根求和，没有更新或单条路径查询接口。 需要修改点值、边映射并查询某个终点时，用 dynamic_tree_path_affine_sum。 空输入返回空数组，单点返回原点值；输入不被修改。 边和映射一一对应，必须形成 \([0,n)\) 上的树，\(n\) 须能由 int 表示。

后序递归算出每个子树经过父边变换后的贡献，并保存在 contribution； 前序换根时直接从父亲答案中减去该贡献，再应用父边求出另一侧的贡献。 每条边执行 4 次标量乘法。答案数组在两趟之间原地复用， 没有额外增加一个 T 数组。邻接表仅存端点和边编号，从输入读取函数系数， 并先按度数预留容量；度数数组在 DFS 中复用为子树大小。

按 T 运算 \(O(1)\) 计，总时间和空间均为 \(O(n)\)；最坏递归深度 \(O(n)\)， T 需支持默认构造、复制、T(int)、+、-、*、+=， 满足环的相应运算规律，T(k) 表示乘法单位元的 \(k\) 倍。 乘法不要求交换，因此也支持矩阵；不需要除法、求逆或相等比较，零乘数有效。 整数运算的所有中间值须可表示；浮点有通常的舍入与相减消去误差。

枚举有标号树与无标号树形

使用 noya/graph/tree_enumeration.hpp，两种接口都枚举无根树， 回调收到 \(n-1\) 条无向边 es。编号均为 \([0,n)\)，区别是编号是否影响计数：

接口 什么算不同的树 \(n=4\) 时的数量
enumerate_labeled_trees(n, work) 边连接到哪些编号不同，就算不同方案 16
enumerate_unlabeled_trees(n, work) 只看树形，换编号后相同的只给一棵 2：链、星形

无标号版本中的编号只是访问数组的下标，不代表这些编号具有区别。 两个接口都不枚举根。\(n=1\) 调用一次回调，边集为空；\(n=0\) 不调用回调。 旧的 enumerate_trees、enumerate_rooted_trees 已由这两个明确区分标号的接口替代。 Prüfer 编解码仍在 noya/graph/prufer_code.hpp，编码和解码均为 \(O(n)\) 时间、 \(O(n)\) 工作空间。编码要求 \(n\ge2\)，输入恰为 \([0,n)\) 上一棵树的 \(n-1\) 条边； 边的顺序和端点方向任意，不会修改输入。解码要求序列元素属于 \([0,\lvert s\rvert+2)\)， 返回的前 \(n-2\) 条边依次为 (当前最小叶子, 序列元素)，最后一条边的端点升序。 空序列解码为 {(0,1)}；单点树由枚举接口单独处理。

最小叶子的扫描指针只向右移动。删去叶子后，只有它的邻居可能成为指针左侧的 新叶子；若有，直接处理，否则继续向右扫描，所以总共只扫描 \(O(n)\) 个位置。 编码用度数和剩余邻居编号的异或值寻找叶子的唯一邻居，不需要邻接表或 DFS。 异或值是精确的删除摘要，不是哈希；它只在度数为 1 时作为邻居编号使用。 输入树和标签范围是前置条件，不提供一般无效图的检测。

例：枚举直径不超过 \(x\) 的树

最直接的写法是“枚举 → 建邻接表 → 求直径 → 筛选”。 这里直径按边数计算，单点树直径为 0：

#include "noya/graph/tree_enumeration.hpp"
#include "noya/graph/tree_diameter.hpp"

long long ans = 0;
noya::enumerate_unlabeled_trees(n, [&](const auto &es) {
  std::vector<std::vector<int>> g(n);
  for (auto [u, v] : es) {
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int d = std::get<0>(noya::tree_diam(g));
  if (d > x) return; // 跳过当前树，继续看下一棵。
  ++ans;            // 或在这里处理符合条件的 es。
});

要枚举有标号树，只把函数名换成 enumerate_labeled_trees。 例如 \(n=4,\ x=2\)，无标号只有星形这一种；有标号则有 4 种，因为每个编号 都可以是中心。\(x=3\) 时，分别有 2 种和 16 种。 完整可运行程序见 test/example/tree_enumeration.cpp：

clang++ -std=c++23 -O2 -I. test/example/tree_enumeration.cpp -o /tmp/tree-enumeration
printf '4 2\n' | /tmp/tree-enumeration
# 输出 1；换成有标号枚举后输出 4。

回调通常写成上面的 void 即可。如果要找到一棵后就结束，可以用返回 bool 的回调：true 继续、false 终止整个枚举，不是跳过当前树。 枚举函数返回 true 表示遍历完成，false 表示被回调提前停止。 边集引用只在本次回调中有效，需要保存时自行复制。

实现为什么这样选

有标号树直接枚举 Prüfer 序列并解码，\(n\ge2\) 时恰有 \(n^{n-2}\) 棵， 每棵 \(O(n)\) 时间、\(O(n)\) 工作空间，检查直径另需 \(O(n)\)。 随意令 \(\mathrm{parent}_i<i\) 会漏掉有标号方案，例如编号为 0-2-1 的链。

无标号树从单点开始，给上一层每种树形的每个点接一个新叶子，再按同构去重。 任何非单点树删去一个叶子都得到更小的树，所以这样不会漏掉树形。 去重复用 tree_isomorphism：给所有候选共用一张类型编号表，尝试各点为根， 取最小的整树类型编号。两个无根树能取到同一种有根树类型，当且仅当它们同构。 这里的临时选根只是为了比较树形，不会增加输出数量；比较使用完整结构， 没有随机哈希碰撞。

这样实现短，也便于检查：在 \(k\) 个点这一层，若上一层有 \(t_{k-1}\) 种树形， 只尝试 \((k-1)t_{k-1}\) 个候选，各做 \(k\) 次有根同构计算。需要保存上一层树形 和本层去重信息；即使回调很早停止，较小点数的各层仍会先生成。 例如 \(n=8\) 时，有标号树有 262144 棵，无标号树形只有 23 种。 无标号数量已核对 OEIS A000055， 测试还用小图的全部边集和顶点重标号独立检查不重不漏。

根树同构与编号复用

tree_isomorphism::solve(g,rt=0) 为每个顶点的有根子树分配精确类型编号。 签名是排序后的完整孩子类型数组，使用 std::map 判等，不是可能碰撞的概率哈希。 无向树的双向邻接表和从 rt 向外的孩子表都可以，要求所有顶点在该根下构成一棵树， 编号、点数及新增类型计数须在 int 范围内。输入不被修改；空输入返回空数组， 不访问 rt，也不改变已有类型表。

比较两棵根树时，要让它们使用同一个分类器：

noya::tree_isomorphism iso;
auto a = iso.solve(first_tree, first_root);
auto b = iso.solve(second_tree, second_root);
bool same = a[first_root] == b[second_root];

mp 和 cnt 跨次保留，首次遇到一种签名才分配新编号，编号按后序分配。 不同分类器或不同历史中的同一个数字，不一定表示同一 树形。复制分类器会复制其独立类型表；之后各自添加的新类型不能直接交叉比较。 需要重新开始一组分类时，可以用 iso = {}; 一起清空表和计数器。

实现保留递归 DFS：先完成孩子，再共用一份签名缓冲区。只在新增类型时复制签名， 已有类型不复制；避免短签名接管过大的缓冲容量并长期留在表中。 缓存叶子编号，避免每片叶子重复查表。 已有序的孩子编号直接使用，递增新键使用末尾插入提示，但一般查找仍是对数复杂度。 单次全新分类器为 \(O(n \log(n+1))\) 时间、\(O(n)\) 空间；已有 \(M\) 种类型时，时间为 \(O(n \log(n+M+1))\)，总空间为 \(O(n+M+L)\)，\(L\) 是保留签名中的整数总数。 递归深度最坏 \(O(n)\)；复用对象的存储不能只按本次树的大小估算。

根树的最小加权逆序排列

rooted_tree_minimum_inversion_order(fa,c,d) 返回 {cst,ord}：ord 是父亲在孩子 之前的顶点排列，\(\mathrm{cst}=\sum_{i<j}d_{\mathrm{ord}_i}c_{\mathrm{ord}_j}\)，在所有合法排列中最小。 fa 必须是一棵非空树的父数组，恰有一个 -1，根可使用任意编号；三个数组长度 相同，输入不会被修改。c,d 均非负，Weight 须容纳块权和、交叉乘积及最终答案； 乘法不会自动提升到更宽类型。数值范围较大时，应直接传入 vector<__int128_t>。

对于两个独立块 \(A\)、\(B\)，\(A\) 在前的代价为 d(A)c(B)，反过来为 d(B)c(A)，因此 优先处理 \(c/d\) 最大的非根块，将它接到当前父块之后。采用交叉乘积比较，不做除法。 \((c,d)=(0,0)\) 排在所有非零块之后；相同比值时块根编号较大者优先， 再比较版本号。

每个活动块的代表就是它最靠近原树根的顶点，只需一条带路径压缩的父链接， 无需额外的按大小合并及标签数组。初始堆一次建好，累计完成 \(n-1\) 次有效收缩即可 停止，不再弹出余下的失效堆项；环形链表记录拼接，倒着填入结果数组。 数值前置条件包括参与计算的块权和、交叉乘积及前缀和。

时间为 \(O(n \log(n+1))\)，空间为 \(O(n)\)，均假定 Weight 运算为常数时间。 只做路径压缩的父链接为均摊 \(O(\log n)\)，单次查找的 递归深度仍可到 \(O(n)\)。

最短路：边权范围与返回值

shortest_path.hpp 保留普通队列、双端队列、二叉堆和逐轮松弛的直接实现。 单源接口要求非空图、合法起点和顶点编号；输入不会被修改，平行边、自环允许存在。

接口 适用范围 时间 额外空间
bfs_unweighted(g,s) 无权图 \(O(V+E)\) \(O(V)\)
bfs01(g,s) 边权为 0 或 1 \(O(V+E)\) \(O(V)\)
dijkstra(g,s) 非负整数边权 \(O(V+E \log(E+2))\) \(O(V+E)\)
bellman_ford(g,s) 整数边权，可有负环 \(O(V+VE)\) \(O(V)\)
find_negative_cycle(n,edges) 寻找任意位置的负环 \(O(V+VE)\) \(O(V)\)
floyd(matrix) 无负环的整数权图 \(O(V^{3})\) \(O(V^{2})\)

前三个单源接口返回 {distance,predecessor}，起点的前驱是自己，不可达点为 -1。 BFS 的不可达距离是 INT_MAX，0-1 BFS 和 Dijkstra 使用 INT64_MAX； Dijkstra 也把无法表示为小于 INT64_MAX 的距离留作该哨兵。 它保留 __int128 加法，避免非最优的大权绕路溢出后变成较短距离；权值和中间和 须能由该类型表示。优先队列可同时含 \(O(E)\) 个旧状态，因此平行边场景的复杂度按 \(\log(E+2)\) 计，不能一概写成 \(\log V\)。

Bellman–Ford 返回 {di1,prv,neg}，neg[v] 表示能从起点到达的负环还能到达 \(v\)。 这类点的距离是 INT64_MIN；有限但超出 int64 的距离也会向相应端点饱和， 所以判断负无穷必须看 neg。内部保留宽距离，中间值必须能由 __int128 表示且 小于 \(2^{120}\)，不会因中途超出 int64 而丢掉后来回到范围内的路径。 它只按原编号顺序扫描有出边的顶点，消除每轮遍历空邻接表的 \(O(V^{2})\) 开销； 完整时间为 \(O(V+VE)\)，辅助空间为 \(O(V)\)。

负环查找返回按环上行进顺序排列的输入边编号，能找到起点之外的负环；没有负环时 返回空数组，支持 \(n=0\)。某轮没有更新即可立即结束；松弛按输入边编号顺序进行。边编号须能由 int 表示，整数权值和中间计算须能由 __int128 表示。

0-1 BFS 在首次弹出顶点时确定距离，用一个字节标记避免旧队列项重复扫描邻接表。 BFS、0-1 BFS、Dijkstra 和 Bellman–Ford 返回时移动数组，不再复制整份结果。 Floyd 将 \(i\to k\) 不可达的整行提前跳过，并缓存两行及 \(i\to k\) 距离，仍用宽整数相加。 其缺边哨兵是 numeric_limits<T>::max()/2，所有有限距离须小于该哨兵并可由 int64 表示；不得输入负环。空矩阵返回空矩阵。

find_path(pre,s,t) 只负责沿合法、无环且能回到 \(s\) 的前驱链恢复路径，复杂度与路径 长度成正比；先判断可达性和 neg，不要给它不可达或负无穷的终点。

数据结构接口

common_interval_decomposition_tree(p) 接受非空的 \(0,\ldots,N-1\) 排列，以候选栈和 并查集在 \(O(N \alpha (N))\) 时间、\(O(N)\) 空间内构造强公共区间树。节点的位置 \([l,r)\) 和值域 \([\mathrm{mn},\mathrm{mx})\) 都是半开区间，ch 按位置顺序排列，lin 区分合点和析点。 两个排列先用其中一个排列的位置映射重标号，再传入另一个排列。

consecutive_segment<T>::assign(l,r,v) 返回覆盖前的分段，保留已有分段的语义， 不自动合并相邻同值段。内部复用边界迭代器，复杂度仍为 \(O(\log K + s)\)。 double_ended_heap<T>::pop(x) 要求集合中存在 \(x\)，删除其中一次出现；延迟删除可能 积压到一次最值查询才清理，内存也包含积压条目，不能按当前存活元素数估算。

dynamic_bitset 的按值运算保持输入不变，返回时移动内部存储，避免额外复制整个 位集。移位把整字搬移、相邻字组合和补零分开处理，保持 \(O(N/64)\) 复杂度。

static_range_inversions<T> 预处理后可按任意顺序查询 \([l,r)\)，统计 \(i<j\) 且 \(a_j<a_i\) 的严格逆序对；相等值不计入，默认空对象和空区间返回零。 构建按值扫描累计块间计数，并按不同值压缩频次数组；重复值较多时可减少存储。 重建可能复用先前的缓冲容量。

static_range_lis_query 接受 \(0,\ldots,N-1\) 的排列，query(l,r) 返回 \([l,r)\) 的 最长严格上升子序列长度。预处理复用 Monge 乘积工作区，小规模分治直接模拟 Seaweed 交叉，单调排列直接生成临界点；普通查询仍使用原来的位向量结构。

static_range_mode<T>::query(l,r) 返回 \([l,r)\) 的众数及频次，并列取最小值， 空区间返回 nullopt。按严格弱序判等，值类型只须可复制、可比较。 构建为 \(O(N\sqrt{N})\)，查询利用出现位置索引扫描边界，为 \(O(\sqrt{N})\)，总空间 \(O(N)\)。 查询不修改共享工作区；支持通过 build 重建，包括 build(data.xs)。

static_range_xor_basis<UInt,B> 的输入须在 \(B\) 位内，预处理为 \(O(NB)\)， 最大/最小异或、可达性和秩查询为 \(O(B)\)，导出约化线性基为 \(O(B^{2})\)。 区间采用 \([l,r)\)；默认空对象也可查询，空区间只含异或值零。 查询种子可使用 UInt 的全部位，超出 \(B\) 位的非零值不可由输入生成。

tag_HashMap<K,V,op> 支持全局加法偏移；op 须满足交换律、结合律及 \(\operatorname{op}(a+t,b+t)=\operatorname{op}(a,b)+t\)，如 min/max。插入值按当前真实值解释，缺失键读取 返回 V() 且不插入。join(rhs) 合并后，rhs 保留合并前较小的映射；两边等大时 先交换。若持续独立复用这些保留的映射，不能套用一次合并树的总复杂度界。

top_k_sum<T> 维护最大的 min(k,size()) 个元素之和，插入返回稳定句柄， 删除时传入原值及句柄。插入/删除为 \(O(\log(N+1))\)，求和为 \(O(1)\)，调整 \(k\) 为均摊 \(O(1+d)\)，其中 \(d\) 是所选数量的变化量。内部通过节点提取和准确插入位置搬移元素； 重复值按句柄区分。累计插入次数须能用 int 表示，T 的差值和中间求和须不溢出。

wavelet_matrix<T,Sum> 支持 \([l,r)\) 上的第 \(k\) 小、频次、值域计数/求和和前驱后继。 按严格弱序压缩，排序等价的值返回同一代表；求和保留各输入自己的 Sum 转换结果。 构建包含比较排序，为 \(O(N \log(N+1))\)；查询为 \(O(\log(\sigma+2))\)，\(\sigma\) 为不同排序类的数量。 默认空对象、空区间、重建及 build(matrix.xs) 均受支持；第 \(k\) 小要求非空有效下标。 Sum 的加减与所有中间值须有效，较宽输入可显式选择 128 位求和类型。

图论接口

best_euler_circuit_count<T>(n,rt,edges,fix) 用 BEST 定理统计有向多重图的 欧拉回路，重边按不同标号计算。fix=true 表示指定 rt 的一条出边为首边； fix=false 统计该起点的所有首边选择。空边集返回 1；非空时起点无出边、 出入度不平衡或有多个活跃连通分量均返回 0。孤立点不参与矩阵，自环只影响阶乘。

实现直接构造矩阵树余子式，选择非自环出度最大的点作为内部矩阵根，避免部分 稀疏图在消元时变稠密；外部起点和首边语义保持不变。度数排序后共享阶乘计算， 无需按最大度数分配阶乘表。 设 \(A\) 为活跃顶点数，时间 \(O(V+E+A^{3})\)、额外空间 \(O(V+A^{2})\)，要求 T 支持域运算。

bipartite_decomposition(nl,nr,edges) 一次返回最大匹配、最小点覆盖及其补集 最大独立集；无孤立点时 ok=true 并返回最小边覆盖，否则 ec 为空。 两侧均为空时 ok=true，所有结果为空。允许重边，输入不被修改；匹配及边覆盖 可随输入边顺序改变，各顶点集合仍按编号递增。连续邻接表保留输入顺序，分层增广 使用递归 DFS，每轮只扫描有边顶点，并复用最后一轮 BFS 的可达性生成点覆盖。 时间 \(O(V+E\sqrt{V})\)，空间 \(O(V+E)\)。

minimum_dag_path_cover 的相邻顶点必须由原图边连接； dag_order_decomposition 返回最大可达性反链和最小链覆盖，链中相邻顶点只需可达。 两者都要求 DAG，并允许重边。后者沿逆拓扑序合并位集，再直接生成闭包邻接表； 设 \(R\) 为可达有序点对数，时间 \(O\left(V+(V+E)\left\lceil\frac{V}{64}\right\rceil+R\sqrt{V}\right)\)， 空间 \(O\left(V+E+V\left\lceil\frac{V}{64}\right\rceil+R\right)\)。\(R\) 仍可能达到 \(O(V^{2})\)。

bipartite_edge_coloring(nl,nr,edges) 按输入边顺序返回 \([0,\Delta)\) 内的颜色， 其中 Delta 是最大度；每个顶点的关联边颜色互异，重边视为不同边，输入不被修改。 颜色方案不保证唯一或字典序最小；空边集直接返回空数组。

实现按度数计数排序后合并低度数顶点，再补成正则二分图；压缩后较大一侧的点数 记作 \(S\)，有 \(S\Delta\le2E\)。偶数度沿闭合迹交替拆分，奇数度用递归分层增广取一个 完美匹配，然后继续递归。标记数组只重置当前子图的边，避免每次清空整个原图。 时间 \(O(V+E\sqrt{S} \log(\Delta+1))\)，空间 \(O(V+E)\)。原边数和补边后的边数均须能用 int 表示。

HopcroftKarp(n,m,edges) 的 l、r 保存匹配对象，未匹配为 -1，ans 是最大匹配数。 允许重边，边数组改为按 const 引用接收，不再原地随机打乱；稳定连续邻接表保留每个 左点的邻边顺序。匹配方案不保证唯一。分层搜索只处理有边的左点，用递归 DFS 寻找增广路； 时间 \(O(V+E\sqrt{V})\)，空间 \(O(V+E)\)。

BipartiteMatching_Dense<BS>(adj,n,m) 借用邻接位集，调用方需保证其生命周期，前 \(n\) 行 宽度相同且至少为 \(m\)；第 \(m\) 位及以后的填充位被忽略。matching() 返回按左点递增的匹配， vertex_cover() 返回两侧最小点覆盖，不改动匹配或输入。增边后可以对每个未匹配左点 调用 bfs(s)，恢复最大匹配后再查询最小点覆盖；不支持修改图的维数或删除匹配边。

稠密版先用空闲右点位集贪心配对，再做增广；同一次构造中复用失败搜索已排除的封闭区域， 公共 bfs(s) 会重新开始搜索，以允许增边。支持 GNU std::bitset 和本库 noya::dynamic_bitset 的按机器字查找；后者需另 include noya/ds/dynamic_bitset.hpp。 Clang/libc++ 的 std::bitset 使用逐位扫描回退，追求跨平台性能时优先选动态位集。 设每行占 \(W\) 个机器字，时间 \(O(V+W+n(nW+m))\)，额外空间 \(O(V+W)\)，邻接矩阵另占 \(O(nW)\)； 逐位扫描回退的时间式中 \(W\) 应改为每行位数。

bipolar_orientation(n,edges,s,t) 返回从 \(s\) 到 \(t\) 的顶点排列，每个中间点都在排列前后 各有至少一个邻点；返回值不是按顶点下标存储的排名。要求 \(n\ge 2\)、源汇不同、端点合法， 并要求原图存在 \(s\)-\(t\) 边；缺少该边或图不适合时返回空数组。忽略自环，允许重边， 不修改输入。排列不保证唯一，调整边的输入顺序可能改变返回方案。

实现使用稳定连续邻接表和递归 DFS，通过 lowpoint 与连通性判定点双连通性，再以 链表插入构造 st 顺序。时间和空间均为 \(O(V+E)\)，不排序邻接表。 Library Checker 的 st_numbering 驱动会按题意补 \(s\)-\(t\) 边，并用原图验证答案； 这个适配属于驱动，不能据此省略直接调用模板时的源汇边要求。

block_cut_forest(n,edges) 的原顶点编号为 \([0,n)\)，分量点编号为 [n,n+blk.size())；blk 保留 lowlink 的分量顺序，bel[u] 是分量下标， tr[u] 中则是分量点编号。每个自环各有一个单点分量，孤立点也单独成块； 保留重边语义。要求总点数 \(n+\text{分量数}\)能用 int 表示。

边集构造会接管临时分解结果，build(const lowlink&) 则独立复制分量，保留调用方 的分解对象。关联表按整行填入，并在重建时复用缓冲区。设 \(B\) 为分量数、\(I\) 为分量 大小之和，已有分解后的构建为 \(O(V+B+I)\)，边集构建为 \(O(V+E+B+I)\)。

lowlink(n,edges) 在线性时间内求割点、桥、点双与边双，is_bridge(eid) 为 \(O(1)\)。 保留递归 DFS，最深 \(O(V)\) 层。点双使用顶点栈提取， 避免按边重复收集端点，再按顶点编号分桶，使每个分量内部仍递增有序。 分量顺序仍为 DFS 完成顺序；真正孤立点在遍历时成块，每个自环单独成块并按输入 边序追加。桥按输入边编号递增，边双编号按分量最小顶点递增。支持重边， 不修改输入；build(n,obj.es) 可以用对象自己保存的边集重建。

centroid_decomposition(g) 接受合法无向树的邻接表，也允许空树；不修改输入。 fa、dep 是点分树的父亲和深度，根父亲为 -1、深度为 0，ord 是分解先序。 初始分量入口为 0；存在两个重心时选靠近当前入口的那个，子分量按重心邻接表顺序 处理。空树的 rt 为 -1，三个数组均为空。

初始子树大小用普通 DFS 计算一次；随后每次沿较大子树移动根时，更新边两侧的大小， 删除重心后直接复用子分量大小，避免反复 DFS 计数。时间 \(O(n \log n)\)、空间 \(O(n)\)。 初始化递归深度为树高，分解本身的递归深度为 \(O(\log n)\)。

chordal_graph(n,edges) 忽略自环并把重边视为一条边，不修改输入。返回的 ord 始终是顶点排列；ok=true 时它是完美消除序，cyc 为空。ok=false 时 cyc 给出长度至少为 4 的无弦环，不在末尾重复起点，此时不能把 ord 当作完美消除序。 证据不保证唯一，调整输入边顺序可能改变返回排列或环。空图返回 ok=true。

连续邻接表用时间戳去重，链式权值桶执行最大基数搜索；按首个后继邻点分组， 一次标记检查同组所有点的完美消除序条件，失败后用一次 BFS 构造无弦环。 包括重边归一化、判定和证据构造在内，时间和空间均为 \(O(V+E)\)，\(E\) 按输入边条数计。

minimum_graph_coloring(n,edges) 精确求最小顶点着色，要求 \(0\le n\le64\)。 沿用忽略自环、归一化重边的语义，不修改输入；col 中颜色为 \([0,k)\)， 空图返回 \(k=0\) 和空数组。最优着色不唯一，不保证特定的颜色编号或分组。

各连通分量独立运行 DSATUR 搜索，颜色编号可以复用，最终色数取各分量最大值。 预存度数，增量维护未着色点的禁色位集；回溯只撤销本层新增加的禁色位。 简单贪心团提供下界，达到下界即停止；仍保留完整搜索以保证精确答案。 时间为 \(O(m+n^{2}+nT)\)，\(T\) 是访问的搜索状态总数，最坏情况仍为指数级； 额外空间和递归深度为 \(O(n)\)。原注释的 \(O(n2^{n})\) 时间、\(O(2^{n})\) 空间不适用于此实现。

chromatic_polynomial<Mint>(n,edges) 返回 \(n+1\) 个按次数升序排列的系数， 要求 \(0\le n<31\)。自环使整个多项式为零，重边不改变答案；空图返回 {1}。 这里的自环语义与忽略自环的 minimum_graph_coloring 不同，沿用各自原有约定。

若点的邻居构成团，删除该点并乘上 x-度数；剩余连通块分别计算并相乘。 独立集的集合幂级数直接给出划分数，再用下降阶乘基生成普通系数，无需求值后插值。 运算只需交换环的加减乘，支持合数模数；使用整数时须保证所有中间值不溢出。 设化简后各连通块大小为 \(k_i\)，时间为 \(O\left(m+n^3+\sum_i k_i^2 2^{k_i}\right)\)， 空间为 \(O\left(n+\max_i k_i 2^{k_i}\right)\)。一般图仍为指数级；弦图等可完全消除的图无需指数数组。

sum_of_clique_products(n,edges,weights) 返回所有非空团的顶点权乘积之和， 不是回调枚举接口。要求合法端点且至少有 \(n\) 个权值；自环和重边不产生额外团。 按原始边计数的度数升序、点编号升序确定乘法顺序，自环在度数中计两次。 每个乘积仍从 T(1) 开始左结合相乘，按前缀深度优先顺序累加，支持非交换权值。 因此，增删重边或自环可能改变非交换乘积的顺序；对普通数值权值不会重复计数。

前向边用连续邻接表存储并去重；固定团的首点后，把候选点压缩到它的前向邻域。 至多 64 个候选点用单个整数位集，更多候选点复用各递归深度的位集缓冲。 邻域无边时直接计算首点与各邻点的贡献，避免建立大型局部位矩阵。 令 \(M\) 为不同的非自环边数、\(D\) 为最大前向度数、\(C\) 为非空团数， 时间为 \(O\left(n\log(n+1)+m+MD+C\left(1+\left\lceil\frac{D}{64}\right\rceil\right)\right)\)，空间为 \(O\left(n+m+D\left\lceil\frac{D}{64}\right\rceil\right)\)， 递归深度为 \(O(D)\)。T 的运算代价另计，所有算术中间值须可表示。

complement_graph_components(n,edges) 在 \(O(V+E)\) 时间和空间内求无向图补图的 连通分量，不显式生成补边；允许自环和重边，不修改输入。各分量以最小编号点开头， 分量内保持按候选编号升序扫描的 BFS 发现顺序，\(n=0\) 时返回空数组。 连续邻接表跳过自环，剩余顶点用数组稳定筛选，输出分量自身兼作 BFS 队列。 扫描时每个保留项对应一条原图边，每个移除项只出现一次；删除分量起点的搬移 也不超过紧接着的扫描，因此数组筛选仍是线性总复杂度。

count_c4_per_edge(n,edges) 按输入边顺序返回每条边参与的简单四环数量， 环的四个顶点必须不同，但允许存在弦。平行边视为不同标号的边，自环返回零， 输入不被修改。

两趟计数排序把平行边分组为带重数的简单图，再按不同邻点数做计数排序。 沿度数顺序缩短连续邻接表，累加两步路径及其逐边贡献，仅清空本轮访问的计数槽。 设 \(m\) 为输入边数，\(M\) 为不同的非自环边数，时间为 \(O(n+m+M\sqrt{M})\)，空间为 \(O(n+m)\)。 要求合法端点、输入边数不超过 INT_MAX，答案和算术中间值须能用 int64_t 表示。

small_cycle_count.hpp 提供三个独立用途：triangle_count(n,edges) 返回三角形总数， four_cycle_count(n,edges) 返回四个不同顶点构成的四环总数，均使用 uint64。 自环和重边（含反向重复）被忽略；四环可以有弦，因此 K4 的四环数是 3。 它与上面的逐边接口不同：这里不把平行边视为不同选择。

weighted_triangle_sum(n,edges,w) 累加三角形的顶点权乘积，要求输入本身为简单图， 不含自环或任何方向的重复边，且恰有 \(n\) 个权值；它不做归一化。 三者均要求 \(n\) 非负和合法端点，\(n=0\) 时返回零，传入的边及权值不会被修改。 计数答案须能由 uint64 表示；泛型权值支持负数，但所有乘法和累加的中间结果须可表示。

三角形按 (度数,顶点编号) 从小到大定向，用保留输入顺序的连续前向邻接表存边， 并以字节数组标记邻居。无权版本直接累加标记；加权版本只在确有三角形时计算乘积。 乘法按定向顺序左结合，累加顺序由首点编号、两条前向边的输入位置决定； 不要求乘法可交换。两个接口共用建图过程，各自累加结果。

四环按同一全序，只在环的最大顶点 \(u\) 计数：枚举两步路径 u-v-w，要求 \(v\) 和 \(w\) 都小于 \(u\)；对于相同 \(w\)，新的中间点 \(v\) 与之前的每一个中间点恰组成一个四环。 用顶点计数数组累加，并只清空本轮触碰的位置，不再为所有邻居对建立哈希表。 每条边从低度点向高度点定向，低度点的前向度数为 \(O(\sqrt{M})\)，总扫描量为 \(\sum_v\deg(v)\operatorname{outdeg}(v)=O(M\sqrt{M})\)，额外空间为 \(O(n+M)\)。星形图因此只需线性核心工作。

设 \(m\) 是原始边数、\(M\) 是不同的非自环边数，两个无权接口总时间为 \(O(n+m \log(m+1)+M\sqrt{M})\)、空间 \(O(n+m)\)；归一化后已有序时跳过排序。 加权三角形没有排序和去重，时间为 \(O(n+m\sqrt{m})\)、空间 \(O(n+m)\)，T 的运算代价另计。

special_spanning_trees.hpp 提供双权乘积最小生成树和切比雪夫最小生成树。 minimum_product_spanning_tree(n,edges) 的边为 (wa,wb,u,v)，返回两种权值的和 s1,s2 以及原始边编号 eid，最小化 \(s_1s_2\)。要求 \(n\ge 1\)、图连通、端点合法， 非自环边的两种权值均非负；允许零权、平行边，自环忽略，单点返回零和空边集。 输入边数须不超过 INT_MAX，每次查询得到的树的两种权值和均须能由 int64 表示。 权值乘积、标量化排序键和方向比较用 signed128；输入不会被修改。

乘积树保留支撑点搜索的递归：以不同线性组合的边权做 Kruskal，找到凸包上的 候选树。每轮先缓存各边的排序键，按 (组合权值,原边编号) 排序；复用选边缓冲， 选满 \(n-1\) 条边就停止。递归只保存两维坐标，保留先左后右的访问顺序。 记两端坐标为 \(l=(l_1,l_2)\)、\(r=(r_1,r_2)\)。 两端之间的非负候选坐标满足 \(s_1\ge l_1\)、\(s_2\ge r_2\)，因此 \(l_1r_2\) 已不小于当前最优乘积时可剪枝。保留原来的平局规则：两端乘积相同 时选第二端，后续只在严格改善时更新；返回的边编号及顺序与原实现一致。 设 \(m\) 为输入边数、\(M\) 为非自环边数、\(Q\) 为实际 MST 查询次数，时间为 \(O(m+Q(n+M \log(M+1)))\)，空间为 \(O(n+m+Q)\)；\(Q\) 依赖输入，不能当成固定轮数。 这不是任意负权的乘积优化算法。例如两点的三条边权为 (-4,2),(-2,4),(-3,3)， 支撑点搜索只得到 −8，而中间边的乘积为 −9，因此非负条件不可省略。

chebyshev_mst(points) 接收 int64 坐标，返回 int64 总权和原点编号对。 边权为 \(\max(\lvert\Delta x\rvert,\lvert\Delta y\rvert)\)；允许重复点，空集和单点返回零及空边集，输入不变。 坐标变换 \((x,y)\mapsto(x+y,x-y)\) 后，曼哈顿距离等于原距离的两倍；使用 signed128 完成变换与中间计算，在至多 \(4n\) 条候选边上做 Kruskal，再将权值除以 2。 时间 \(O(n \log(n+1))\)，空间 \(O(n)\)，最终总权必须能由 int64 表示。 每条返回边的端点递增；并列最优时，边集与输出顺序可以不同于旧的完全图 Kruskal。

steiner_tree(g,terminals) 求非负权无向图中连通全部终端的最小代价；邻接表的 每条无向边须在两端各存一次。steiner_tree_with_edges(n,edges,terminals) 接收 steiner_tree_edge<Weight>{a,b,w}，返回权值 w 与递增、无重复的原边编号 eid。 允许重边、自环、重复终端和非连通图，输入不变。空终端集或唯一终端的答案为零， 恢复接口返回空边集。端点须合法，边权有限且非负，点数和原边编号须能用 int 表示； 并列最优时不保证固定边集。

两接口都先检查终端是否连通，再分配 DP 表。固定排序后的最后一个终端为最终根， 仅枚举其余 \(k-1\) 个终端的子集。DP 仍先在同一点合并两组终端，再做多源 Dijkstra； 初始堆一次建成，最后一轮在固定根出堆时结束。这样 DP 行数从 \(2^{k}\) 减为 \(2^{k-1}\)，合并项从 \(3^{k}\) 降为 \(3^{k-1}\) 的量级，恢复过程仍直接递归。

numeric_limits<Weight>::max() 作为不可达或代价无法表示的哨兵，有限答案必须 严格小于它；恢复失败时边集为空。子集合并与沿边松弛都先检查加法范围，避免 某个很大的非最优候选溢出后污染小答案。整数恢复会核对选边和；浮点使用普通 舍入运算，按边编号累加的恢复权值可能与 DP 的不同加法顺序有微小差异。

令 \(t\) 为传入的终端个数、\(k\) 为去重后的个数、\(r=\max(k-1,0)\)。总时间为 \(O(t \log(t+1)+n+m+3^{r} n+2^{r}(n+m) \log(n+m+2))\)，空间 \(O(t+2^{r} n+n+m)\)。 这是小终端数的指数算法；不同终端最多为 unsigned 的位数，且整张 DP 表必须放得下。 大路径的递归恢复

strongly_connected_components(n,edges) 返回按拓扑序排列的强连通分量列表， 每个分量内的点号递增。它不直接构造缩点 DAG，也不直接返回点到分量的映射； 需要映射时遍历返回列表即可。允许空图、自环、平行边和非连通图，输入不变。 要求 \(0\le n<\mathrm{INT\_MAX}\)、端点合法、原边数不超过 INT_MAX。

实现保留 ACL 的递归 Tarjan 顺序，但直接从传入的边表建立连续邻接表， 不再经 add_edge 复制整张边表。递归返回当前点的 low 值，省去独立 low 数组； 已结束分量的访问编号置为 \(n\)，使它们不再降低活动点的 low 值。DFS 仍按点号启动， 邻接边保持输入顺序，最终反转分量编号，分量编号与 DFS 的访问顺序有关。 构造返回列表前释放遍历数组。时间和额外空间均为 \(O(n+m)\)，递归深度最坏 \(O(n)\)，

three_edge_connected_components(g) 返回无向多重图中，删去至多两条边后仍互相 连通的极大点集。非自环边须在两个邻接表中各出现一次，重边的反向副本数须匹配； 自环忽略，允许空图、非连通图和平行边。点数、邻接项总数须能用 int 表示，端点合法， 输入不变。各分量以最小点号开头，按最小点号递增排列；分量内其余点保持循环链表的 合并顺序，不保证排序。

连通性是在整个原图中判断的，连接路径可以经过分量外的点。例如 0 和 1 之间有 三条内部点不相交的路径时，两端可以同属一个三边连通分量；路径上的度数为 2 的点 仍各自成组，所以该分量的诱导子图不一定连通。

实现使用线性 DFS、未完成链与循环分量合并。泛型 lambda 负责递归， DFS 使用独立的紧凑位标记。重边只跳过一条父边，其余父向边仍按回边处理。 时间 \(O(n+m)\)，额外空间 \(O(n)\)，输入邻接表另占 \(O(n+m)\)；递归深度最坏 \(O(n)\)， 输出分量的访问标记使用位压缩表示。

tree_contour(g,initial) 在静态无向树上维护两套独立的值： point_add(u,x) 只影响 range_sum(u,l,r)，后者求与 \(u\) 的距离落在 [\(l\),\(r\)) 内的 点权和；range_add(u,l,r,x) 只影响 point_get(v)。两套值都从 initial 开始， 一种更新不会进入另一种查询。initial 为空表示全零，否则长度须等于点数。 允许空树；非空输入须是端点合法的无向树，不支持森林、自环或重边。 不修改或持有输入图；拷贝后的对象拥有独立状态。

点分治为每个点记录重心祖先及距离。查询累加重心桶，减去与查询点同分支的桶。 初值先按距离直接累加，再线性构建各桶的 Fenwick，构造从 \(O(n \log^{2}n)\) 降为 \(O(n \log n)\)。递归收集距离，移动重心时沿边调整并复用子树大小，避免重复全组件扫描。 区间查询在同一趟祖先遍历中处理两端。距离端点允许任意 int 且 \(l\le r\)；先截到 [0,\(n\)] 再减祖先距离，避免 INT_MIN-distance 溢出，负距离和超过树直径的部分自然为空。

每次更新或查询 \(O(\log^{2}n)\)，空间 \(O(n \log n)\)，构造递归深度最坏 \(O(n)\)。 点数不超过 INT_MAX-2；权值、更新值的相反数、桶内累加及 所有算术中间值须能用 long long 表示。

tree_decomposition_width_two(n,edges) 识别树宽是否至多为 2，并返回对应的树分解。 输入须为合法简单无向图：\(n\ge 0\)，端点在 [0,\(n\)) 内，无自环和重复无序边；允许空图、 非连通图，输入不变。树宽超过 2 时返回 nullopt；否则 ba1 有 \(n\) 个大小至多为 3 的袋，es 用袋编号连接成一棵树，非空时有 \(n-1\) 条边。w 是这些袋的最大大小减一， 空图约定为 0；它不保证是最小树宽。例如边为 (0,2),(2,1) 的路径，本算法仍可给出 宽度为 2 的合法分解。输出包含袋、各袋中的顶点以及连接边。

不断消去当前度数不超过 2 的点，有两个邻居时补上它们之间的边；逆序恢复袋，并接到 含其剩余邻居的已有袋。每个点最多记录两个邻居，因此改用固定两个槽；消点后的度数 同时记录有效槽数。消点时的边哈希表在恢复阶段复用为“最后含此边的袋”，省去第二张表。 提前统计度数并预留邻接表容量；非空图最小度超过 2，或 \(n\ge 2\) 时边数超过 \(2n-3\)， 都可直接判定失败。时间期望 \(O(n+m)\)，空间 \(O(n+m)\)，期望界依赖哈希表表现；没有递归。

find_directed_cycle(n,edges) 返回沿环遍历的输入边编号； find_undirected_cycle(n,edges) 返回对齐的顶点、边编号，使 es[i] 连接 vs[i] 与下一个顶点。无环时返回 nullopt。自环为长度 1 的环， 无向平行边可构成长度 2 的环；有向同向平行边本身不构成环。 连续邻接表保留输入边顺序，递归 DFS 按点编号启动搜索，路径数组用于恢复环。 保持原来的证据顺序。时间和空间均为 \(O(V+E)\)，输入边数须能用 int 表示。

cycle_detection_directed(g) 只返回是否有环，用 FIFO 消入度实现 \(O(V+E)\) 时间、 \(O(V)\) 额外空间；不再为布尔结果维护最小堆。topological_sort(g) 仍返回字典序 最小的拓扑序，有环时返回空数组，时间为 \(O(E+V \log(V+1))\)，额外空间为 \(O(V)\)。 两者均要求合法端点，顶点数及每个顶点的入度须能用 int 表示；空图判环为 false。

cycle_detection_undirected(edges) 按输入边做按大小合并与路径压缩，每条边只查 两次根。时间为 \(O(V+E \alpha (V))\)，额外空间为 \(O(V)\)；这里 \(V\) 是最大顶点编号加一， 编号须在 \([0,\mathrm{INT\_MAX})\)，空边集直接返回 false。所有找环、判环和拓扑接口均不修改输入。

directed_mst(n,root,edges) 求以 root 为根的最小树形图，边为 (权值,起点,终点)。 返回总权值和原始输入边编号；根不能到达所有点时返回 nullopt，单点返回零和空数组。 允许负权、平行边、自环；自环和进入根的边被忽略，不修改输入。平行边只保留 权值最小者，同权取原始编号最小者。

按终点分组去重后，两两合并建立左偏堆；缩环时统一减去已选入边权值， 用标记跳过尚无增量的下推。缩环和结果展开均为迭代过程，只有左偏堆合并使用 对数深度递归。设 \(m\) 为输入边数，\(M\) 为不同的有效有向点对数， 时间为 \(O(n+m+M \log(n+1))\)，空间为 \(O(n+m)\)。去重和分组在部分稀疏图上有额外常数。

要求 \(0<n\le\mathrm{INT\_MAX}/2\)、合法端点及不超过 INT_MAX 条输入边。 权值支持零初始化、复制、<、一元 - 和 +=，满足有序加法运算语义， 所有中间值须可表示；不要求 ==。浮点舍入可能影响并列边的选择，不保证逐位相同。

dominator_tree(g,root) 返回每个点的直接支配点：根返回自身，不可达点返回 -1。 支持自环、重边和不可达分量，不修改输入；要求合法根、合法端点和 int 可表示的点数。 DFS 编号与 link-eval 路径压缩均直接使用递归。

先遍历根可达部分，再为这些点建立连续反向邻接表，跳过自环及进入根的边。 每个点只入桶一次，用 head/next 数组代替各桶的动态数组；半支配点直接存 DFS 序号，减少间接访问。仍为简单 link-eval 的 Lengauer–Tarjan 算法，时间 \(O(V+E \log(V+1))\)、空间 \(O(V+E)\)，不是平衡 link-eval 版本的反阿克曼界。只可达根时直接返回，避免为不可达分量建立反图。

dsu_on_tree(g,add,qry,del) 固定以 0 为根，要求连通树；既可传双向邻接表， 也可传以 0 为根的孩子表。输入不被修改，空树不调用任何回调。 依次处理轻子树，保留重子树；合并某个轻子树时，先对其中所有 \(x\) 调用 qry(u,x)，再逐点 add(x)。因此查询不会把同一轻子树内部的点对混入跨子树贡献。

随后调用 qry(u,u) 和 add(u)：前一个时刻，统计状态恰好包含 \(u\) 的全部真后代， 还没有 \(u\) 自身。轻子树处理完会逐点 del，根处理完保留全树状态。 同大小重儿子取邻接表中最先出现者，子树内部按重儿子优先序扫描。

只保存一个重儿子数组。先递归选重儿子，再按“轻子树清空、重子树保留、合并轻子树” 的顺序递归处理；查询、加入和清空直接遍历对应子树，调用深度为 \(O(\text{树高})\)。 预处理 \(O(n)\)，回调次数 \(O(n \log n)\)，额外空间 \(O(n)\)；实际时间另乘回调本身的代价。

rerooting_dp(g,uni,merge,ae,av,rt=0) 在静态无向树上计算以每个顶点为根的 DP。 merge 须满足结合律，以 uni 为双侧单位元，不要求交换；贡献严格按每个顶点 原邻接表中的顺序合并。ae(value,from,to) 把 from 一侧的根状态传过边， av(value,u) 将邻居贡献合并值封闭成以 \(u\) 为根的状态。

返回数组第 \(u\) 项等于从 \(u\) 独立递归计算整棵树的结果。rt 只决定计算顺序， 不会改变结果或邻接顺序。要求 \(g\) 为双向邻接表表示的树、编号及点数在 int 范围内； 非空树的 rt 必须合法，空树直接返回空数组。输入不会被修改。 状态 T 需可复制和赋值，不要求默认构造；回调应对相同参数给出相同值，不能修改 输入状态。回调的跨顶点调用顺序、重复次数不是接口保证，不能依赖外部计数来生成结果。

两次递归 DFS 分别处理子树贡献和父侧贡献。每条无向边的两个方向各计算一次 ae， 避免重复变换；换根时共用一份最大度数大小的前缀数组，用一个累计后缀完成排除。 先算完所有孩子的父侧状态，再递归孩子，因此不会覆盖尚需使用的前缀。 总计 \(O(n)\) 次状态转移和 \(O(n)\) 个状态对象；若 T 的复制、合并或变换不是 \(O(1)\)， 实际代价须另计。递归深度最坏 \(O(n)\)。 递归栈和复制所需空间也取决于状态类型 T 的大小。

dynamic_rerooting_dp<Path,Point,Info,vtx,cmp,rk,ae,av> 用顶树维护动态森林的换根 DP。 cmp 按路径顺序合并，不要求交换；rk 合并轻子树，须满足结合律和交换律。 ae 把路径簇转为点簇，av 将轻子树贡献接到一个点上；这些纯函数须满足对应 树 DP 的簇合并规则。query(rt) 查询以 rt 为根的全树聚合， query_subtree(rt,u) 查询同一连通块内、以 rt 为根时 \(u\) 的子树聚合。

link(a,b) 要求两个点来自不同连通块，cut(a,b) 要求这条边存在，所有编号须合法。 底层指针接口的 link(v,parent) 还要求 \(v\) 是当前树根，cut(v) 删除当前父边； 查询和 evert 会改变当前根。get_info 为 \(O(1)\)，其余动态操作均摊 \(O(\log n)\)， 按每次 DP 运算 \(O(1)\) 计；空间按已创建顶点数计为 \(O(n)\)。

节点由对象共享拥有，复制对象仍指向同一片森林，修改会相互可见。 底层节点指针在存储扩容和对象移动时保持有效，直到最后一个共享持有者释放； 调用者不再手动删除节点。最后一个持有者析构会在 \(O(n)\) 时间内释放全部节点， 虚子树节点通过空闲表复用。

旋转只维护路径聚合，顶点自身的 DP 单独缓存；辅助树根的虚边句柄随旋转转移， 无需事先沿父指针扫描整条路径。子树查询直接读取暴露后端点的缓存值， 不再临时拆开并恢复祖先路径。所有结构维护和清理均不使用递归。

dynamic_star_min_cut(n,edges,weights) 在固定非负无向图外加一个中心点，维护中心到 原图各点的星形边。set_star_weight(u,w) 修改一条星形边并返回全局最小割； global_min_cut() 为 \(O(1)\) 查询。支持重边、零权和不连通图，自环被忽略； 构造不修改输入，复制对象得到独立状态。要求 \(1\le n\le\mathrm{INT\_MAX}/4\)、合法端点， 所有边权及星形边权非负，原图非自环边权总和加当前星形边权总和始终小于 \(2^{60}\)。

保留最小邻接顺序的 pendant-pair 收缩建树。收缩后的平行边合并，已删除簇的邻接表 连同容量释放，避免保留逐轮产生的旧缓冲。用父编号大于子编号的性质迭代计算重链； 边界权通过两端加权、LCA 减两倍权值的树上差分计算，最后一次性建线段树。 这一后处理从 \(O(mn+n \log^{2}n)\) 降为 \(O(m \log(n+1)+n)\)，收缩仍是总预处理的主要开销。

区间加、全局最小值的线段树保留标记而不下推：父亲最小值为自身标记加两个孩子的 较小值；修改星形边转为叶子到根的重链区间加。同值赋值直接返回。 总预处理 \(O(n(n+m) \log(n+m+1))\)，单次修改 \(O(\log^{2}(n+1))\)；简单图的预处理可写为 \(O(n(n+m) \log(n+1))\)。构造峰值空间 \(O(n+m)\)，完成后仅保留 \(O(n)\) 状态。

dynamic_tree_path_affine_sum<Mint>(values,edges,affine) 的拓扑固定为一棵非空树。 第 \(e\) 条无向边在两个方向均使用同一个映射 \(f_e(x)=\mathrm{mul}\,x+\mathrm{add}\)；不是逆函数。 set_vertex(u,x) 修改点值，set_edge(e,mul,add) 修改边映射。 query(r) 把每个点 \(v\) 的值沿 \(v\)→\(r\) 的路径依次应用边函数，再对所有 \(v\) 求和： 离 \(r\) 最近的函数在最外层，\(r\) 自己贡献未经变换的点值。它不提供连边、断边或单条路径查询。

例如链 0—1—2，点值为 (2,3,5)、边映射为 \((2x+1,3x+4)\)， 查询根 0 得到 \(2+(2\cdot3+1)+(2(3\cdot5+4)+1)=48\)，根 2 的答案为 37。 每条边被拆成一个携带仿射函数的顶树节点，沿用 dynamic_rerooting_dp； 复制封装仍共享同一棵树的更新，移动和最后一个共享持有者的释放规则与底层一致。

要求输入点数、边编号及 \(2n-1\) 可由 int 表示，边数组与映射数组等长且构成树。 Mint 满足交换半环运算，默认值为零，支持从 0/1 构造、复制、加法、乘法； 不要求相等比较、减法或除法。计数也用 Mint 表示，无需转回整数或访问模数。 按 Mint 运算 \(O(1)\) 计，构造 \(O(n \log n)\)，修改和换根查询均摊 \(O(\log n)\)，空间 \(O(n)\)。

dynamic_tree_subtree(values) 维护可连边、断边的森林，支持 vertex_add(u,delta)、 subtree_add(u,parent,delta) 和 subtree_sum(u,parent)。子树接口的两个点必须相邻： 作用范围是把边 (u,parent) 概念上删除后 \(u\) 所在的一侧，parent 不是任意指定的根。 link(a,b) 要求来自不同连通块，cut(a,b) 要求边已存在。空森林有效，编号为 \([0,n)\)。

保留带虚子树大小、和及差分懒标记的 LCT。把 parent 设为根并暴露 \(u\) 后， \(u\) 的左辅助子树属于祖先侧，\(u\) 自己加虚子树就是目标侧。因此查询直接取 \(\mathrm{val}+\mathrm{vs}\)； 修改只更新这一侧的统计量，并同步左孩子的已接收标记，使增量不会传到祖先侧。 子树操作不再实际断边、接边。虚实孩子交换保持总大小、总和不变，避免重新汇总； 已换根的点连边时省去一次重复 access，点加直接维护缓存和，零增量不再传播。

节点由对象拥有，因内部存储直接指针，保持不可复制、不可移动。 支持负点值与负增量，要求点数可由 int 表示，所有和、乘积及累积懒标记运算可由 long long 表示；不能只保证最终查询答案不溢出。构造 \(O(n)\)，动态操作均摊 \(O(\log(n+1))\)，size() 为 \(O(1)\)，空间 \(O(n)\)。树操作及清理均为迭代过程。

euler_walk_directed(n,edges,start=-1) 与 euler_walk_undirected 返回可选的 euler_walk_result{vs,eid}，分别记录顶点序列和输入边编号。支持自环、重边； 要求 \(n\) 非负、端点合法、边数可由 int 表示，不修改输入。 指定起点不在 \([0,n)\)、度数不符或无法覆盖全部边时返回 nullopt。

自动起点的选择规则：无向开迹选编号最小的奇度点，有向开迹选唯一的出度减入度为 1 的点；回路选编号最小的非孤立点。每个点按输入边顺序取边。 无边时返回单点 {start}（默认 0）；\(n=0\) 且 \(\mathrm{start}=-1\) 返回两个空数组。

先检查度数和起点，再用 size_t 偏移构造连续邻接表，逆序填充保持行内输入顺序。 有向图每条边只有一份邻接项，不建立访问标记；无向图使用字节标记跳过边的另一份。 Hierholzer 的遍历栈占用结果数组的前缀，回退时把答案写入后缀： “写入位置减栈顶位置”始终等于尚未使用的边数，因此两部分不会互相覆盖。 不再分配独立遍历栈或反转最终答案；结束时仍有未用边即判定失败。 总时间和空间均为 \(O(n+m)\)，空边集为 \(O(1)\)，全过程无递归。

directed_eulerian_trail / undirected_eulerian_trail 共用上面的核心， 返回类型为 eulerian_trail_result{vs,eid}，两个 vector 直接移动， 不复制结果。它们要求 \(-1\le\mathrm{start}<n\)，越界起点属于违反前置条件； euler_walk_* 则对越界起点返回 nullopt。其他合法输入的起点选择、空图结果、 取边顺序与 euler_walk_* 相同。包含 noya/graph/eulerian_trail.hpp。 共用实现省去重复算法和零散邻接表分配，时间/空间仍为 \(O(n+m)\)，空边集 \(O(1)\)。

maximum_matching(n,edges) 求一般无向多重图的最大基数匹配，返回 {匹配边数, mate}，未匹配点的 mate 为 -1。要求 \(n\) 非负、端点在 \([0,n)\)； 自环忽略，重边允许，不修改输入。返回任意最大匹配，不保证字典序最小。

采用 Gabow 的 Edmonds 缩花搜索。先贪心匹配直接相邻的空闲点，再搜索增广路， 因此贪心只提供初始匹配，不影响最终最大性。连续邻接表保留输入取边顺序； 每个空闲根仅搜索一次，以根编号标记当前搜索，不再反复清空全图数组。 缩花用惰性代表点及路径压缩，不再逐次扫描全图重写花基；恢复匹配直接递归展开 交错路与花的两侧。空图、纯自环和大量孤立点不触发无效搜索。 按该缩花实现的保守界，时间 \(O(n+m+nm \log(n+1))\)，空间 \(O(n+m)\)。

general_weighted_matching<Cost,TotalCost=Cost>(n,edges) 接收 (u,v,w)， 返回 weighted_matching_result<TotalCost>{wt,es}：最大总权和实际配对。 要求 \(n\) 非负、端点在 \([0,n)\)、无自环、权值为非负整数；允许重边， 返回某一对端点时按这对点间最大的边权计入答案。每对按 \(u<v\) 返回，整体按 \(u\) 排序。 不修改输入，也不保证在总权相同时匹配数最多或字典序最小。

保留 Gabow 的对偶与堆维护核心，只在所有正权边等权时启用已有的紧边初始匹配。 等权时所有边起始约化权为零，先取得一个合法匹配，再继续缩花搜索保证最优。 混合权值时直接进行缩花搜索。 零权边不影响最大总权，直接略去；过滤后无边则返回零权、空配对，不分配 \(n\) 规模数组。 总时间 \(O(n+m+nm \log(n+1))\)、空间 \(O(n+m)\)；全零输入时间 \(O(m)\)、额外空间 \(O(1)\)，空输入 \(O(1)\)。

输出求和时，每条边先还原原权值再累加，避免“最终答案能表示、两倍答案却溢出”。 Cost 仍需容纳边权倍增及内部对偶/懒标记运算，有效事件值不能碰到内部无穷大哨兵； TotalCost 用于约化权值计算和最终求和，也必须足够宽，不能只看最终答案。 例如较大总权可用 general_weighted_matching<long long,__int128_t>。 匹配恢复和花结构遍历使用递归。

global_min_cut(matrix) 用 Stoer–Wagner 求无向图全局最小割，返回 {割权, 升序排列的一个割侧}。输入必须是方形、对称、非负、对角为零的邻接矩阵； 所有权值及累加、收缩后的容量均须有限且能由 T 表示。按值传参保留左值输入， 不再使用矩阵时可传 std::move(matrix)。\(n=0\) 返回 {0,{}}，\(n=1\) 返回 {0,{0}}。

每阶段按最小原编号打破平局，只在严格更优时更新割侧。 只扫描仍未加入的候选点，把连接权更新和选最大值合成一趟；缓存当前最大值， 并稳定删除已选点，使平局规则无需额外比较。顶点组使用追加式链表，每次收缩 \(O(1)\) 拼接；记录最佳组的首尾端点，之后即使该组被扩展或吸收，也能恢复当时的完整割侧。 不再复制整组顶点，其他工作区为 \(O(n)\)，含矩阵副本的空间仍为 \(O(n^{2})\)。

某阶段找到零割即可结束，零矩阵只需一阶段 \(O(n^{2})\)，一般最坏时间仍为 \(O(n^{3})\)。 不使用正负无穷大数值哨兵；首个合法割必定记录，割权可以等于类型最大值。 无符号容量、宽整数及只支持所需比较/累加的容量类型可用。

gomory_hu_tree<Cap>(n,edges) 把无向非负容量图的任意两点最小割编码为一棵树， 仍返回三个公开字段 {fa,cut,tr}；支持重边，忽略自环和零容量边，不修改输入。 所有两点最小割和实际容量运算须能由 Cap 表示。\(n=0\) 返回三个空数组， \(n=1\) 返回单点树；min_cut(s,s) 返回 numeric_limits<Cap>::max()。

只创建一次 ACL 流网络，每次求流前恢复初始残量。通常用两条残量弧表示一条无向边： ACL 边容量设为 \(2c\)、初始流设为 c，两个方向的初始残量恰为 \(c\)。 若 \(2c\) 无法表示，则使用两条有向边。 保持原编号次序，只把 0 号点和有正容量非自环邻边的点放进流网络； 其余孤立点保留零权接到 0 的输出形式。输出记录父亲、割权和树的邻接表。

设压缩后有 \(k\) 个点，最多调用 \(k-1\) 次最大流，其他时间 \(O(n+m+k^{2}+km)\)， 总空间 \(O(n+m)\)，另加最大流工作区。全零边、纯自环和无边图只需 \(O(n+m)\) 时间。 仍使用 ACL 的递归 Dinic，并未消除最大流内部递归。 min_cut(s,t) 只读取有效树 tr，支持手工构造结果；从 \(s\) 递归找到 \(t\)， 沿途维护边权最小值。查询最坏 \(O(n)\) 时间、\(O(n)\) 调用栈，同点查询为 \(O(1)\)。

hungarian<T,MIN>(cost) 支持 \(n\times m\) 矩形费用矩阵，要求每行长度相同且 \(n\le m\)； 每行恰好匹配一列，每列至多匹配一行。MIN=true 求最小费用，false 求最大费用， 返回 {费用, 每行匹配列, 行势能, 列势能}。最大化时势能仍对应 -cost 的最小化问题， 与原接口一致；输入不修改，空矩阵返回 {0,{},{},{}}。

直接读取原矩阵，辅助空间为 \(O(n+m)\)。 把上一轮未访问列的松弛量减法并入下一轮扫描，只遍历实际访问过的列更新势能； 增广结束后停止更新松弛量。时间为 \(O(n^{2}m)\)。 输出数组通过移动返回，避免再次复制。

首轮直接初始化松弛量，选列使用独立状态，不把类型最大值当作未找到候选。 费用直接累加，省去虚拟列 Y[0] 保存的相反数；这修复了最小化单个最小负值时的 额外取负溢出。T 必须支持有符号费用、加减与比较，所有实际中间值和累计费用须可表示； 最大化还要求每个费用取负及转换后的计算可表示。

incremental_minimum_spanning_forest<Weight>(n) 在只增边的图上维护最小生成森林。 边权在整个插入流中互异，边 ID 为全局互异的非负 int，可以不连续、 不按插入次序递增。add_edge(a,b,w,id) 返回 -1 表示森林多了一条边；否则返回被移除的 边 ID，新边被拒绝时返回它自己的 id。自环总是拒绝，允许重边、负权和不连通图。

连通性只会合并，另用并查集维护；替换环上的最大边不会改变连通分量。 内部动态树只维护路径最大边的节点编号，省去通用 LCT 的大小和双向聚合， 保持迭代 splay 与翻转下传。连接新边时先把 \(a\) 换到根，把独立边节点接在 \(a\) 和 \(b\) 之间； 因边节点已是 \(a\) 所在树的新根，无需再换一次根或重复检查连通性。

最多使用 \(n-1\) 个可复用边槽位，槽位直接保存当前边 ID 与两个端点。 存储不随外部 ID 或已移除边的数量增长，支持 INT_MAX ID。原图顶点不参与最大值比较，不使用数值负无穷哨兵； 有符号最小值、无符号零权和只提供 < 的有序权值类型均可使用。 构建 \(O(n)\)，每次插边均摊 \(O(\log(n+1))\)，空间 \(O(n)\)，与插入次数和 ID 大小无关。 本接口的复制和移动由独立的数组状态支持。

incremental_scc_merge_times(n, edges) 离线处理整段插边序列。 对第 id 条边，返回不早于 \(\mathrm{id}+1\)、且两端首次同属一个 SCC 的前缀长度； 永远不同属一个 SCC 时返回 \(m+1\)。自环、插入前两端就已同属 SCC 的边返回 \(\mathrm{id}+1\)， 并非 \(m+1\)。按返回时间合并边的两端，可以还原每个前缀的 SCC 划分。 顶点编号为 \([0,n)\)，边数 \(m\) 小于 INT_MAX，输入数组不会被修改。

先求最终图的 SCC，只剔除跨最终分量、永远不可能合并的边，再对时间区间分治。 左右子问题共用一个边数组的不同区间，内部 SCC 使用递归 Tarjan 和复用的 CSR 工作区，不在父层保留子图副本或分量列表。右半区缩点形成的自环直接记录插入时刻。 时间为 \(O(n+m \log(m+1))\)，空间为 \(O(n+m)\)；图的 DFS 最深 \(O(n)\)， 时间分治有 \(O(\log(m+1))\) 层递归。全为 DAG 时，最终分量筛选可直接结束。

incremental_scc_pair_product_sums(weights, edges) 返回每次插边后， 同一 SCC 内不同顶点无序对的权值乘积和。按时间排列的事件使用扁平链表， 保留同一时刻按输入边 ID 递增处理的顺序和按大小合并的平局规则； 普通整数、模整数及浮点权值均可使用，实际中间值须可表示。空边序列直接返回空数组。

johnson(n, edges) 返回有向图的全源最短路矩阵；任意连通块中存在负环时返回 nullopt。顶点编号为 \([0,n)\)，边数不超过 INT_MAX；整数边权及内部势能、 重赋权与还原运算须可用 __int128 表示，每个有限最短距离须可用 int64_t 表示。不可达使用 int64_t::max()，有限距离恰好等于该值时编码相同。输入不会被修改。

Bellman–Ford 保持按输入边顺序扫描，邻接表改用 CSR；各源点共用堆的容量。 64 位路径直接使用结果行作为距离数组，省去每个源点额外的距离数组分配和初始化； 势能还原仍逐项写回结果。 重赋权后的距离可能超过 64 位，即使还原后的真实距离完全可表示。用“最大重赋权边权 × \(\max(1,n-1)\)”作为保守上界： 严格小于 INT64_MAX 时使用 64 位，否则自动使用 128 位距离与一个复用的工作行。 判断覆盖最多 \(n-1\) 条边的简单最短路，并避免有限距离撞上内部无穷标记。 实际用除法检查这个上界，避免特别大的无用边导致上界乘法溢出；仍支持 __int128 边权。

允许重边时，二叉堆可能同时保存 \(O(m)\) 个候选，完整时间界为 \(O(nm+n^{2}+nm \log(m+2))\)，空间为 \(O(n^{2}+n+m)\)。输出本身就需要 \(O(n^{2})\) 空间。

k_shortest_walk_lengths(n, edges, s, t, cnt) 按递增顺序返回有向游走的长度， 允许重复顶点、重复边和零权环；重边按不同的边分别计数，\(s=t\) 时包含长度 0 的空游走。 边权须非负，运算须精确；普通整数及能保持精确运算的二进制小数均可使用。 只返回 Weight 能表示的长度，不足 cnt 项时返回已有项，恰好等于类型最大值的长度也有效。 输入保持不变；顶点、边数和内部可持久化堆节点使用 int 编号。

反向 Dijkstra 的有效出队顺序已保证最短路树中父亲在儿子之前，即使边权为零也成立， 因此不再另外构造孩子表和 BFS 序。反向遍历结束后，将同一组 CSR 缓冲改建为正向邻接表。 每个顶点先用 make_heap 在线性时间内建立局部堆；完全二叉堆满足左偏性质， 再与父亲的可持久化堆合并一次，避免每条非树边都复制一条堆路径。 时间为 \(O((n+m)\log(m+2)+\mathrm{cnt} \log(\mathrm{cnt}+2))\)，空间为 \(O(n+m+n \log(m+2)+\mathrm{cnt})\)； 允许任意重边时，堆的对数应按边数计。

到达状态与距离分开保存，不再用类型最大值的四分之一截断可达性。 边权与距离相加前检查范围，旁路代价先做非负差，再加剩余项； 替换候选时也先计算堆中代价的差，避免“先溢出、后抵消”。超出类型范围的候选 可以丢弃，因为后续增加的旁路代价均非负。只取一项时在起点出队后直接返回； 结果数组按实际输出增长，有限条路径配合很大的 cnt 不会预先分配 cnt 个元素。

lower_bound_flow<Cap> 支持非负的边流量下界、上界。add_edge(u,v,lo,hi) 返回原边编号；feasible_circulation() 返回可行环流的逐边流量， max_flow(s,t) 返回最大非负流值 val 与逐边流量 flw，无解时返回 nullopt。 如果只有负的 \(s\)→\(t\) 流可行，max_flow(s,t) 也返回无解；交换端点是不同的查询。 自环、重边、固定流量边均保留原编号；查询不改变公开的 n、es， 修改它们或继续加边后可以重新查询，不需要清理缓存。

先按各边下界计算顶点收支，再建立容量为 \(\mathrm{hi}-\mathrm{lo}\) 的残量图。 自环直接取下界，固定流量边只参与收支；环流收支已经平衡时直接返回下界。 有源汇查询先用 \(t\)→\(s\) 回边找可行流，清空所有辅助边后，再在原残量图上增广。 没有收支缺口时省去可行性最大流。残量边成对连续存储，邻接表使用 CSR， 阻塞流使用递归 DFS，最深 \(O(n)\) 层。

最大流答案须能由 Cap 表示，所有运算须精确；普通整数和精确二进制小数可用。 整数容量按非自环边下界之和做保守检查：能够放进 Cap 时保持原类型， 否则将小于 64 位的整数扩为无符号 64 位，其余扩为无符号 128 位。 因此每条边容量可表示、但顶点需求或总需求超过 Cap 的合法实例也可以处理。 使用 128 位输入时仍须保证每个顶点的入边下界和、出边下界和及总正需求 不超过内部无符号 128 位范围；不提供任意精度计算。恰好等于 Cap 最大值的答案有效。

准备工作 \(O(n+m)\)，至多两次 Dinic；令 \(V=n+2\)、\(E\le m+n+1\)，最坏时间为 \(O(n+m+V^{2}E)\)，空间 \(O(n+m)\)。顶点及残量弧使用 int 编号。

manhattan_edges(xs,ys) 或 manhattan_edges(points) 为平面点集生成至多 \(4n\) 条 曼哈顿 MST 候选边，按 (weight,u,v) 排序，点号对应输入下标。空点集返回空数组， 重合点保留不同下标；两个坐标数组必须等长，点数须能由 int 表示。 它只生成候选边；需要 MST 时再调用 minimum_spanning_tree，后者的总权重使用 int64_t。候选边的权重类型仍与坐标相同，所有生成的边权必须能由该类型表示。

四方向扫描使用有序表，时间 \(O(n \log n)\)、空间 \(O(n)\)。缓存每轮的排序键，并复用扫描 停止处的插入位置，避免二次查找。小于 64 位的整数使用有符号 64 位中间量， 64 位整数使用有符号 128 位中间量，因此允许靠近类型极值的坐标，只要返回边权可表示。 有符号 128 位及浮点输入仍须保证中间求和、作差和取负不溢出，浮点坐标须有限， 并受通常的舍入误差影响。传入的点集或坐标数组不被修改。

spanning_tree_count(n,edges) 返回无向生成树的加权总和，每棵树贡献所选边权之积。 in_arborescence_count(n,root,edges) 计数边沿路径指向 root 的有向生成树； 每个非根顶点恰好选一条出边，根不选出边。自环不参与，两种函数都保留平行边、 零权和负权的代数意义，不修改输入。无向 \(n=0\) 或 \(n=1\) 返回 1； 有向版要求 \(n>0\)、root 合法，\(n=1\) 返回 1。

权重类型必须支持域运算，例如素数模数的 modint。连通图的加权答案也可能因抵消 而为 0，不能把模意义下的对角元素为 0 当成孤立点。普通整数除法和任意合数模数 不满足这个前提。

无向版先用非零、非自环边检查连通性，再删除度数最大的顶点构造余子式； 若最后一点也有最大度数，则仍删除最后一点。有向版固定删除调用方指定的根，直接构造 (\(n-1\)) 阶矩阵， 省去完整 \(n\) 阶矩阵及其复制；若某个非根点没有非零出边，则直接返回 0。 连通性已经成立、或所有非根点都已找到非零出边后，停止对应的预检查。 两者在边数不足 \(n-1\) 时也直接返回 0。共享的行列式实现保持独立。

按域运算为常数计，无向版时间 \(O(n^{3}+m \alpha (n))\)，有向版时间 \(O(n^{3}+m)\)，空间 \(O(n^{2})\)。 这些是稠密矩阵算法；提前返回并不代表任意十万点连通图都能在线性空间内处理。

maximum_clique(n,edges) 与 maximum_independent_set(n,edges) 分别返回 无向图的一个最大团、一个最大独立集，要求 \(0\le n\le64\)、端点在 \([0,n)\) 内。 \(n=0\) 时返回空数组，自环和重边忽略，不修改输入。只保证方案大小最优， 不保证字典序、顶点输出顺序，也不保证与旧实现选择同一组最优顶点。

两者共享 64 位邻接掩码和贪心着色剪枝的递归搜索；独立集直接将邻接掩码取补， 省去补图边表。先按所求图的补图连通块拆分：不同块之间两两相连， 各块的最大团可以合并。每层着色只用一个预留容量的向量， 另用候选点数做上界剪枝。最坏时间仍为指数级，保守上界 \(O(n 2^{n}+m)\)， 峰值辅助空间 \(O(n^{2})\)、递归深度 \(O(n)\)；64 点是表示上限，不保证任意 64 点图都很快。

maximum_weight_closure(weights,dependencies) 求最大权闭包： 依赖 (u,v) 表示选 \(u\) 就必须选 \(v\)，收益可以为负，允许选空集。 返回 w 为最大总收益，sel 按顶点编号递增排列；并列最优时返回所有最优闭包 的交集，即包含关系下最小的最优方案。自环、重复依赖不改变答案，输入保持不变。

权值使用 int64_t，所有正权之和须不超过 INT64_MAX，允许单点权值为 INT64_MIN。 顶点和建图边数须能用 int 编号。无正权时返回空集，无依赖或全部严格正权时直接取 正权点。一般情况先缩强连通分量，因为同一分量中的点必须一起选或一起不选， 再用分量编号构造最小割网络，省去每个分量单独的顶点向量。 分量总权用 128 位累加，容量使用无符号 64 位： 令 \(P\) 为缩点后的正权总和，依赖容量取 \(P+1\)，负权容量大于 \(P+1\) 时截为 \(P+1\)。 空集对应容量为 \(P\) 的割，所以这种截断不会改变任何最小割。

缩点时间 \(O(n+m)\)；若缩点后有 \(k\) 个点、\(e\) 条跨分量依赖，随后 Dinic 的最坏时间为 \(O(k^{2}(k+e))\)，总辅助空间 \(O(n+m)\)。SCC 与最大流都保留递归，深度 \(O(n)\)。

MinCostFlow<Flow,Cost,objective,SCALING_FACTOR> 用容量缩放求带上下界的 最小或最大费用 \(b\)-flow。顶点约定为“流出减流入等于供给”，add_supply(v,x) 增加供给，add_demand(v,x) 减少供给；边允许负下界、负上界、自环和平行边， 但必须满足 \(\mathrm{lower}\le\mathrm{upper}\)。objective 默认为 MINIMIZE，也可取 MAXIMIZE； 整数缩放因子至少为 2，默认 2。

solve() 返回 (Status,Cost)，第二项按传入的原始边费用计；仅在 OPTIMAL 时表示可行最优费用。总费用较大时用 solve<__int128>()，保留较窄的 最短路费用类型，只扩大乘积和总费用的计算。每对正反残量边仅计一次费用， 避免先求两倍总费用造成额外溢出。旧的 get_result_value<T>() 保留内部 最小化目标的符号，因此 MAXIMIZE 时它是原总费用的相反数； 边句柄的 cost() / gain() 分别返回内部费用及其相反数。

Flow 必须是有符号整数，须容纳容量差、累计供需、算法中的 excess 及相关取负； Cost 须容纳边费用、取负、势差和最短路运算，有限距离必须小于其最大值， 该最大值用作不可达标记。总费用类型须容纳操作数、乘积及累加中间值； 扩大总费用类型不会同时扩大容量或最短路类型。需要更大容量/势范围时， 可分别将 Flow / Cost 设为 __int128。初始缩放单位取不超过最大量级的 因子幂，避免向上倍增越过整数上界。

get_potential() 在 solve() 之后返回规范化的势：在最终残量图外加入一个 到所有点费用为 0 的源点，取其最短距离。实现利用已有合法势重赋权后跑 Dijkstra，并保留后续 get_cut() 所需的搜索状态。INFEASIBLE 时可调用 get_cut() 取得不相容的割证书； 空集也可能是证书，应以 solve() 的状态判断是否有解。

可以继续增点、增边、追加供需后再次 solve()；供需操作是增量，不是覆盖旧值。 已有边句柄在同一对象增点增边时仍有效，复制或移动对象不会重绑定旧句柄。 并列最优流的具体选择不作固定保证。

令 \(V\)、\(E\) 为点数和原边数，\(U\) 为初始残量容量或供需的最大绝对量级。 固定缩放因子时，求解的保守上界为 \(O((V+E)^{2} \log(V+E+1) \log(U+1))\)； 规范化势为 \(O((V+E) \log(V+E+1))\)，辅助空间 \(O(V+E)\)。 本轮主要加速势与证书的生成，求解主体仍是容量缩放。

minimum_diameter_spanning_tree<Weight>(n, edges) 在非空、连通、非负边权 无向图中构造直径最小的生成树，返回 dia 和原始输入中的边编号 eid。 允许零权边、重边和自环；自环不会入树。单点图返回直径 0 和空边集。 输入不变，输出恰有 \(n-1\) 条不同的边；并列最优时不保证固定的边集或顺序。

算法枚举位于顶点或边内部的绝对中心，再构造以该中心为根的最短路树。 重复 Dijkstra 求全源距离，其有效出队顺序已经按距离递增，反转后可直接 用于中心扫描，零权边产生的距离并列不需要额外排序。严格长于两端最短路 的边不能提供更优中心，可以跳过。内部中心用双源 Dijkstra 构树，不复制 增广图。整数边权的两个中心偏移有相同的半整数部分，统一舍去这一部分 不改变最短路选择，因此不必把所有边权乘二。

去掉自环后若恰有 \(n-1\) 条边，利用连通性直接按树做递归直径 DP；一般图若 第一次最短路发现所有点距离都是 0，也立即返回该零权生成树。这两种情况 不会分配二次规模的距离矩阵。

通常使用整数 Weight。有限最短距离和最优直径必须严格小于该类型最大值， 最大值保留为不可达标记。松弛与候选直径在相加前检查是否可能改善，避免 无用的大权绕路、两倍偏心距等中间值溢出；不要求所有输入边权之和可表示。 支持有符号、无符号整数与 __int128；浮点数仍受自身舍入误差影响。 不接受空图、不连通图或负权。

一般情形时间 \(O(V(V+E) \log(V+E+1)+VE)\)，空间 \(O(V^{2}+E)\)；树输入时间、空间 均 \(O(V+E)\)，递归深度最坏 \(O(V)\)。 零直径一般图只需一次 Dijkstra，时间 \(O((V+E) \log(V+E+1))\)、空间 \(O(V+E)\)。

minimum_mean_cycle<Weight>(n, edges) 返回有向图中环的最小平均边权， 即“环上边权总和 / 边数”，返回类型为 optional<long double>；无环时为 nullopt，空图也如此。允许负权、零权、自环、重边和不连通图，不修改输入。 函数只返回平均值，不返回具体环。

先分别处理自环，再拆强连通分量；跨分量的边不属于任何环，无需参与后续 DP。 每个需要计算的分量都从全零距离开始，用 Karp 公式求值： 令 \(d_{k,v}\) 为恰走 \(k\) 条边到 \(v\) 的最小权和，分量有 \(s\) 个点，则答案为

\[ \min_v\max_{0\le k<s}\frac{d_{s,v}-d_{k,v}}{s-k}. \]

DP 与最后的比值计算都按行连续访问，存储完整 DP 表。

强连通分量若恰有 \(s\) 条非自环边，就是一个单环，可以直接求平均；等权分量 直接取该权值。若该分量的最小边权已不小于当前答案，也无需继续计算。 所有有效候选仍是输入图中的环，不会把跨分量的很小权值当作答案。

设需要跑 DP 的分量点边数为 \(V_c\)、\(E_c\)，时间为 \(O\left(V+E+\sum_c V_c E_c\right)\)，辅助空间为 \(O\left(V+E+\max_c V_c^2\right)\)，含最坏 \(O(V)\) 的递归 SCC 深度。 树状 DAG、单环和大量很小的分量不再需要整图二次空间；一个巨大的复杂 强连通分量仍需二次 DP 空间。

这是浮点近似接口，不是精确有理数接口。边权须能转换为有限 long double， 中间权和、差值也须保持有限；有效精度由平台的 long double 决定。 大整数转换和很接近的权和相减可能丢失精度，使用更宽的整数输入类型不会 自动使内部运算变成精确整数运算。

minimum_spanning_tree(n, edges)、maximum_spanning_tree(n, edges) 和 prim_dense(n, edges) 的边均按 (权值, 起点, 终点) 传入，与许多图模板 的 (起点, 终点, 权值) 顺序不同。返回 (int64_t 总权, 原始边编号数组)， 不修改输入。图不连通时返回覆盖每个连通分量的生成森林；空图返回 0 和空数组。 允许负权、重边和自环，自环不参与森林；并列最优时不保证固定边集或顺序。

前两个函数使用 Kruskal，把排序所需字段和原编号放在连续数组里，避免比较时 反复跳转到输入边；不要求复制整个输入边对象。排序只比较权值，已按所需权值方向 排好序时会跳过排序，连通时选满 \(n-1\) 条边后停止扫描。最大生成森林按权值降序处理， 不会把负权边取反，因此也能处理最小有符号整数边权。

prim_dense 使用连续的 \(n\times n\) 边编号表，在每个尚未访问的连通分量重新开始。 旧实现只处理 0 号点所在分量，此处已修正为完整森林。Kruskal 通用情形时间 \(O(V+E \log(E+1))\)，已有序时 \(O(V+E \alpha (V+1))\)，辅助空间 \(O(V+E)\)；缓存排序键的 常数空间比只存边下标更大。dense Prim 时间 \(O(V^{2}+E)\)，辅助空间 \(O(V^{2}+V)\)， 应在稠密且规模适合二次矩阵时使用。

三个接口面向整数边权，使用有符号 __int128 累加，最后返回 int64_t； 最终总权必须可由 int64_t 表示。64 位边权允许中间累计和超出 64 位范围。 若使用 128 位边权，还须保证权值及累加中间量不超出有符号 128 位范围。 点数、边数和边编号使用 int 范围；不提供浮点或任意精度总权重接口。

offline_dynamic_component_sum<T>(values) 离线处理无向图的加边、删边、 点权增量与连通块权值和。初始图没有边，初始点权由 values 给出。 add_edge(u,v) 加入一个副本，remove_edge(u,v) 删除一个尚存副本； 两个端点的顺序无关，删边时必须存在该边。支持平行边、自环和负增量。 add_vertex(u,delta) 是增加点权，不能当作赋值；add_query(u) 返回答案下标， solve() 按这些下标返回所有答案，不修改初值或事件，可以重复调用或继续追加事件。

线段树的叶子只保留查询时刻；节点存原事件编号，不复制边或增量对象。 同一条边的多个副本用计数维护，只在副本数从 0 变为正数、再回到 0 时形成 一个有效区间。没有查询能观察到的短暂边不会进入分治，自环不参与合并。 并查集按大小合并、不做路径压缩，使用递归遍历时间线段树，深度 \(O(\log(K+1))\)； 不连通图和没有任何查询的操作序列也可以处理。

不超过 64 位的标准整数点权（不含 bool）使用持续更新：按时间顺序只执行一次每个点权增量， 沿该点的并查集父链更新所有子树和。撤销合并时，从原父根的当前和里减去子根的当前和， 因此已经发生的点权更新不会被撤销。这把增量处理从 \(O(U \log(K+1) \log(V+1))\) 降到 \(O(U \log(V+1))\)。内部使用有符号或无符号 128 位累计，有符号查询答案必须能由 T 表示；无符号答案保持 T 的模 \(2^{\text{位宽}}\)语义。点数及事件数须在 int 范围内。

其他类型仍把增量挂在后缀区间，并保存旧和回滚。T 须可默认构造、复制，支持结合且 交换的 +=，不要求减法；自定义聚合值、模整数以及 128 位整数可沿这条路径使用。 其实际中间和须能由 T 表示，浮点结果可能受求和顺序影响。类型分支由模板在编译时选择， 调用接口不变。

令 \(Q\) 为事件数、\(K\) 为查询数、\(U\) 为增量数、\(E\) 为合并平行副本后的边有效区间数。 整数路径时间 \(O(V+Q \log(Q+1)+(E \log(K+1)+U+K) \log(V+1))\)， 辅助空间 \(O(V+Q+E \log(K+1))\)；其他类型额外需要 \(O(U \log(K+1) \log(V+1))\) 时间与 \(O(U \log(K+1))\) 空间。 这里仍是离线算法，必须先记录需要求解的事件。

offline_dynamic_connectivity(n) 从 \(n\) 个孤立点开始，离线记录无向图的 add_edge(u,v)、remove_edge(u,v) 与 add_query(u,v)。 点号从 0 开始；加边插入一个副本，删边要求存在尚未删除的副本，两个端点的顺序无关。 支持自环、平行边和不连通图；合法点总与自身连通。 add_query 返回答案下标，solve() 返回 vector<bool>，不修改事件或点数， 可以重复求解，也可以继续追加事件后重新求解。

时间线段树只保留查询时刻，节点存原事件编号。同一条边通过副本计数合并有效区间， 自环及查询之间已消失的边不进入时间树；未删除的边持续到最后一次查询。 有序表使用尾部插入提示，顺序加入边时可减少查找；一般顺序仍有对数复杂度保证。 边区间安排完毕即清空活动边表，再使用共享的回滚并查集进行递归分治。 只为真正连接两个不同分量的合并保留回滚记录，因此一次快照内至多保留 \(n-1\) 条记录； 共享 rollback_dsu 的逐次 undo() 接口和无效合并记录约定不变。

没有查询时直接返回空答案；没有任何查询能观察到非自环边时，只比较每个查询的两点是否相同， 不分配 \(n\) 个点的并查集或时间树。这种情况可以处理很大的点号范围。 其余情况下，令 \(Q\) 为事件数、\(K\) 为查询数、\(E\) 为合并副本后的有效边区间数， 时间 \(O(n+Q \log(Q+1)+(E \log(K+1)+K) \log(n+1))\)， 辅助空间 \(O(n+Q+E \log(K+1))\)。递归深度 \(O(\log(K+1))\)，点数和事件数须在 int 范围内。

AC 自动机：多模式匹配与计数

aho_corasick<sig> 接受 \([0,\mathrm{sig})\) 的整数字符。先用 add(pattern) 加入非空模式串， 再调用一次 build()；构建后不能追加模式。每次插入返回独立的模式编号，重复串也不合并编号。 字符串接口 add/match/count_matches(s, base) 默认 base='a'，按无符号字节减去 无符号 base 映射，不建立临时整数数组；完整字节数据可用 <256> 和 base=0，支持 NUL。 所有映射后的字符都须落在字母表内，状态数、模式数与文本长度须在 int 范围内。

match(text) 返回 (结束位置, 模式编号)，结束位置从 0 开始且包含该字符。 结果先按结束位置递增，同一位置按模式长度递减，同一个重复串按插入编号递增。 count_matches(text) 返回每个模式的出现次数，支持重叠；它将访问次数沿失败链倒序累加， 不会展开全部匹配。模式很多或输出量很大、只需次数时应使用此接口。 空文本返回空匹配与全零计数；空模式集合也可以构建，任意合法文本返回空结果。

公开的 nd 保留 trie 插入顺序编号。fa 是 trie 父状态，lnk 是最长真后缀状态， dl 是最近的真后缀终止状态或 -1，out 只存本状态结束的模式编号；不复制失败链输出。 pat 将模式编号映射到终止状态。ord 从根 0 开始按 BFS 顺序排列，同层按父状态处理顺序、 孩子字符顺序排列；构建直接复用该数组作队列。build() 后 nxt 是补全的转移表， 可用 transition(state, character) 扫描。构建时先复制失败状态的转移行，再恢复实际孩子。

令 \(L\) 为全部模式字符数、\(S\) 为状态数、\(P\) 为模式数、\(n\) 为文本长度、\(z\) 为匹配输出数。 构造总时间 \(O(L+S \mathrm{sig})\)，存储 \(O(S(\mathrm{sig}+1)+P)\)；匹配时间 \(O(n+z)\)，额外空间 \(O(z)\)； 计数时间 \(O(n+S+P)\)，额外空间 \(O(S+P)\)。这里的空间包含返回结果。 字母表越大，每个节点的定长转移表越大；这是稠密字母表实现。

双端回文树

deque_palindromic_tree<Char, Compare> 支持 push_front/push_back(ch)、 pop_front/pop_back() 和 clear()，实时维护当前串的所有不同非空回文子串。 删除要求非空。size/empty 查询当前长度，distinct_palindromes() 返回不同回文个数， longest_prefix_palindrome() 和 longest_suffix_palindrome() 返回最长回文前缀、后缀长度； 空串三项回文查询均返回 0。clear() 后可以继续使用，重复清空也合法。 对象不可复制、不可移动；它拥有节点和字符副本，修改插入时使用的字符变量不影响树。

Char 须支持复制、移动和相等比较，Compare 须可默认构造并提供严格弱序， 其等价类须与 == 一致；可以使用非整数字符及降序比较器。 转移用有序 map 保存，字符集无需预先给定。新节点通过 lower_bound 查找插入位置， 用同一迭代器作插入提示，避免重复查找；删除时借用当前端点字符，避免复制字符对象。 quick link 跳过相同扩展字符的失败链段，surface 计数与失败链入边数判断回文的最后一次出现。

文本存于两个方向相反的 vector。删除的一侧为空时，把另一侧的一半搬过来， 先预留目标容量；扩容或搬移可能使单次操作达到 \(O(n)\)，不能宣称每次 push 都是最坏 \(O(\log n)\)。 按字符复制、移动、比较均为 \(O(1)\) 计，push 摊还 \(O(\log(n+2)+\log(\sigma+2))\)， pop 摊还 \(O(\log(\sigma+2))\)，查询 \(O(1)\)，清空 \(O(n \log(\sigma+2))\)。 其中 \(n\) 是当前长度，\(\sigma\) 是字符种类数。实际分配空间为 \(O(N)\)，\(N\) 是历史峰值长度； 删除会释放消失的回文节点，但 vector 容量可保留到对象销毁。长度须在 int 范围内。

KMP：前缀函数与单模式匹配

prefix_function(s) 返回每个前缀的最长真 border 长度：pre[i] 是 \(s[0:i+1]\) 的最长相同前后缀长度，不能取整个 \(s[0:i+1]\)。例如 ababa 得到 [0,0,1,2,3]，空序列返回空数组。

kmp_search(text, pattern) 返回所有匹配的起始下标，按升序排列，允许重叠。 空模式匹配文本的全部 \(n+1\) 个边界，包含末尾 \(n\)；模式比文本长时直接返回空数组。 两种函数均支持 std::string 与 std::vector<T>，字符串直接遍历原字节， 无需构造临时字符数组，支持嵌入 NUL 和高位字节。 T 只需相等比较，不要求可默认构造或复制；vector<bool> 的代理访问也可用。 输入长度及空模式的 \(n+1\) 须在 int 范围内，比较运算需满足正常相等语义。

前缀函数在常数时间比较下为 \(O(n)\) 时间、\(O(n)\) 返回空间。 搜索为 \(O(n+m)\) 时间、\(O(m+z)\) 空间，其中 \(m\) 是模式长度，\(z\) 是匹配数；空间包含返回值。 保留标准的失败链回退循环，匹配成功后退到最长真 border，因而不会漏掉重叠匹配。 字符串与整数接口共享同一实现。

最长公共子串

longest_common_substring(a, b) 接受两个 std::string_view，返回 {l1,r1,l2,r2}，满足 \(a[l_1:r_1]=b[l_2:r_2]\)，且长度在所有公共连续子串中最大。 任一输入为空或没有非空公共子串时返回四个 0。位置相对于各自传入的 view， 可以直接传较大字符串的切片或互相重叠的 view；输入不会被修改。

算法把无符号字节映射到 \(1,\ldots,256\)，中间加入唯一的 0 分隔符，再构造后缀数组； 因此原始数据中的 NUL 和 0xff 都是普通字符。不同来源的相邻后缀给出候选答案。 相同最大长度选择后缀序中最靠前的跨来源相邻对，保持确定的四个返回下标。

Kasai 扫描直接更新最优答案，只保留后缀名次数组，无需保存完整 LCP 数组。 扫描仍计算所有相邻后缀的 LCP，再检查是否跨来源，从而保留线性的摊还时间界。 令 \(N=\lvert a\rvert+\lvert b\rvert+1\)，非空输入的时间与空间均为 \(O(N)\)，任一输入为空时为 \(O(1)\)。 \(N\) 须在 int 范围内。拼接数组一次分配后填入，LCP 阶段少保存 \(N-1\) 个整数； 后缀数组构造还有自身的临时空间，因此这不等于整体峰值内存减少同样的比例。

Lyndon 分解

lyndon(s) 把序列分解为字典序非增的 Lyndon 串，返回包含 0 和 \(n\) 的边界数组。 相邻边界 \([b_i,b_{i+1})\) 对应一个非空因子；例如 ababa 得到 [0,2,4,5]， 即 ab | ab | a。空输入返回 {0}，表示没有因子。 Lyndon 串严格小于它的每个非平凡循环移位，因而不能是某个更短串的重复。 在一致的字符顺序下，这个非增分解唯一。

支持 std::vector<T> 与 std::string，保留标准 Duval 扫描。 字符串直接读取原字符，不再创建临时 vector<char>；T 不要求可复制或默认构造， 但 < 与 <= 须给出正常且一致的顺序，vector<bool> 也可用。 字符串沿用原生 char 的比较规则，NUL 是普通字符；高位字节的顺序会随 char 的符号性变化。 需要固定 \(0,\ldots,255\) 字节序时使用 vector<unsigned char>。

令 \(n\) 为长度、\(f\) 为因子数，常数时间比较下总时间 \(O(n)\)，返回边界空间 \(O(f+1)\)， 其余辅助空间 \(O(1)\)。没有预留 \(n+1\) 个结果位置，因子很少时只需相应大小的返回存储。 输入不会被修改，\(n+1\) 须在 int 范围内；本接口只返回分解边界。

Manacher：所有中心的最长回文

manacher(s) 返回长度 \(2n-1\) 的数组 \(p\)；空输入返回空数组。 \(p_{2i}\) 是以字符 \(i\) 为中心的最长奇回文长度，\(p_{2i+1}\) 是以 \(i\) 与 \(i+1\) 之间的间隙为中心的最长偶回文长度。这里的值是原序列中的完整长度， 不是向一侧延伸的字符数。例如 abba 返回 [1,0,1,4,1,0,1]。 中心 \(c\) 对应的回文区间为 \(\left[\frac{c+1-p_c}2,\frac{c+1+p_c}2\right)\)。

算法把中心下标加倍，直接比较原序列中下一对待扩展字符，不构造分隔符序列。 已知回文在加倍坐标下的边界为 \(m-p_m\) 和 \(r=m+p_m\)； 当 \(c\) 在右边界内时，从镜像中心 \(m-(c-m)\) 取得初值，并截断到 \(r-c\)， 随后每匹配一对字符，长度加 2。奇中心初始长度为 1，偶中心为 0。 每次需要真正向外扩展时推进最右边界，保证常数时间相等比较下总时间为 \(O(n)\)。

支持 std::string 与 std::vector<T>，保留显式元素类型模板参数。 字符只需正常的相等语义；负数、NUL、高位字节、无符号整数均是普通符号， 不需要与任何哨兵值避让。T 无须可复制或默认构造，vector<bool> 也可用。 字符串直接读取原字节，结果不依赖 char 的符号性；输入不会被修改。 只分配返回数组，空间为 \(O(n)\)，其余辅助空间 \(O(1)\)；\(2n\) 须在 int 范围内。

最小表示法：循环旋转的规范形式

minimal_string_index(vector<T>) 返回字典序最小旋转的起点；若有多个相同的最小旋转， 返回其中最小的下标。空序列返回 0。minimal_string(vector<T>) 和 minimal_string(string) 返回对应旋转的副本，空输入返回空结果。 例如 [3,1,2,3,1,2] 的最小起点是 1，旋转结果为 [1,2,3,1,2,3]。

扫描保留候选起点 \(i\)、\(j\) 和已匹配长度 \(k\)。遇到首个不相等字符时， 较差一侧从该起点到该起点加 \(k\) 的候选均可排除，因此直接前进 \(k+1\)。 \(i+k\) 与 \(j+k\) 均小于 \(2n\)，超过 \(n\) 时减一次 \(n\) 即可，无需逐次取模。 字符使用一致的 == 与 > 比较；\(2n\) 须在 int 范围内。

字符串直接比较原生 char，不创建中间字符数组；高位字节的顺序沿用 char 的符号性， 因此不保证与 std::string 的无符号字节字典序相同。NUL 是普通字符。 需要固定 \(0,\ldots,255\) 顺序时传入 vector<unsigned char>。 向量下标接口可接受不可复制的元素，旋转副本要求元素可复制，但不要求默认构造。 vector<bool> 也可用，所有接口均不修改输入。

比较与复制均为常数时间时，总时间 \(O(n)\)。下标接口只用 \(O(1)\) 空间； 旋转接口预留返回容量，再依次追加尾段和前段，返回空间 \(O(n)\)，其余辅助空间 \(O(1)\)。 字符串小于短串优化容量时可以不分配堆空间；这里不承诺每次调用的具体分配次数。

在线 \(Z\) 函数：追加字符与确定事件

online_z_algo<S> 从空序列开始，依次调用 add(i,c) 追加字符， \(i\) 必须恰好等于追加前的长度，即从 0 连续编号。query(j) 返回当前序列中 从 \(j\) 开始与整个序列前缀相同的最大长度；查询位置须满足 \(0\le j<\text{当前长度}\)。 query(0) 始终等于当前长度。S 需要可复制，并提供正常的 != 比较； 不要求默认构造、数值类型或字符排序，负数、NUL、高位字节和 bool 均可用。 输入长度须在 int 范围内。

add 返回本次首次遇到失配、因而已经确定最终 \(Z\) 值的起点。 一个起点最多返回一次，0 从不返回；如果匹配仍然抵达当前串尾， 其值会随未来追加继续变化，暂不返回。调用者不必等待事件才能查询当前 \(Z\) 值。 例如先加入 aaa，三个位置的当前值为 [3,2,1]，但没有确定事件； 再加入 b 后值为 [4,2,1,0]，本次返回 [3,1,2]。 返回顺序为：本次新起点的零匹配在前，其余按在线传播顺序输出， 不承诺下标排序。

内部 \(z\) 使用 -1 表示尚未遇到失配，\(p\) 指向待处理的最早起点。 mp 按首次失配的位置保存正长度匹配的起点，供当前前缀匹配继续传播； 每个非零起点至多确定一次。每追加一个字符仅追加一个空桶， 默认复制结构可独立继续追加，已有状态不受影响。

字符操作为常数时间时，\(n\) 次追加的总时间 \(O(n)\)，单次追加最坏可达 \(O(n)\)， 例如 aaaa...a 后突然加入 b；query 为 \(O(1)\)。结构空间 \(O(n)\)， 一次返回的事件数组也最多 \(O(n)\)；若保存全部返回结果，总事件个数仍至多 \(n-1\)。 这里的“在线”表示可以随时取得当前答案，不表示每次 add 都有最坏 \(O(1)\) 保证。

回文自动机：不同回文与两类父链接

palindromic_automaton<sig> 使用固定大小的转移数组，extend(c) 要求 \(0\le c<\mathrm{sig}\)，返回追加后的最长回文后缀节点编号。默认 \(\mathrm{sig}=26\)； 处理字节时使用 \(\mathrm{sig}=256\)，并先把原生 char 转为 unsigned char，再转为整数， 避免把高位字节当成负数。输入长度 \(n\) 满足 \(n+2\) 在 int 范围内。

nd[0] 是长度 0 的偶根，nd[1] 是长度 −1 的奇根，size() 包含这两个根。 每个真实节点代表一个不同的非空回文；节点按首次出现顺序编号，之后保持不变。 每次追加至多创建一个新节点；lst 是当前最长后缀，sn[i] 记录第 \(i\) 次追加的返回节点。 s 在实际字符前额外保存一个 −1 哨兵，输入字符不与它冲突。

节点的 fa 和 fal 含义不同：

  • fa 去掉两端字符后对应的内部回文；单字符的 fa 是奇根，长度 2 的 fa 是偶根。
  • fal 是最长真回文后缀；单字符的 fal 是偶根。

例如 aaa 的 fa 对应 a，fal 对应 aa。 nd[u].nxt[c] 表示在回文 \(u\) 两端都加 \(c\) 得到的节点，0 表示该转移尚不存在。 两个根的 fa 均为 −1，fal 分别为 1 和 0；不要对根沿 fal 无限遍历。

cnt 只累计节点被 lst 访问的次数，不直接等于该回文在完整串中的出现次数。 例如加入 aaaa 后，a、aa、aaa、aaaa 的原始 cnt 均为 1。 要取得全部出现次数，先复制每个节点的 cnt，再按节点编号从大到小， 仅对真实节点执行 occ[nd[v].fal] += occ[v]，得到 [4,3,2,1]。 保留 cnt 可继续在线追加，避免重复汇总已经累加过的数值。

节点直接在 nd 中原地构造，避免先创建带整个转移数组的临时 Node。 默认复制可独立继续追加。 设 \(m\) 为包含根的节点数，\(m\le n+2\)，总构造时间 \(O(n+m\cdot \mathrm{sig})\)，空间 \(O(n+m\cdot \mathrm{sig})\)。 字符表固定时总时间为 \(O(n)\)；一次失败链扫描可能线性，扩容还可能搬迁已有节点， 所以单次 extend 不保证最坏常数时间。get_fail 是追加流程的内部辅助操作。

前缀与子串 LCS：按查询范围推进

prefix_substring_lcs(a,b,qs) 离线回答 \(\operatorname{LCS}(a[0:\mathrm{pre}],b[l:r])\)， 按 qs 的原顺序返回长度；重复、乱序查询均可。区间为半开区间，要求 \(0\le\mathrm{pre}\le\lvert a\rvert\)、\(0\le l\le r\le\lvert b\rvert\)，序列长度和查询数可用 int 表示。 两个序列只需提供 size、下标访问及稳定的相等比较，不要求排序、数值哨兵或复制元素； 可用于 string、整数数组、span、string_view 和 vector。

每推进 \(a\) 的一个字符，seaweed 扫描维护 \(b\) 各列的端点 to；始终有 \(-1\le\mathrm{to}_j\le j\)。 区间 \([l,r)\) 的 LCS 长度等于 \(r-l\) 减去 \(j<r\ \land\ \mathrm{to}_j\ge l\) 的端点个数。 例如 \(a\) 为 ab、\(b\) 为 cab，端点初值为 [0,1,2]；加入 \(a\) 后为 [0,-1,2]， 查询子串 \(b[1:3]\)（即 ab）时，缺额是 1，所以答案为 1；加入 \(b\) 后为 [0,-1,-1]，答案为 2。 同一前缀的查询按右端点分桶，用树状数组扫一遍即可计算这些缺额。

空前缀或空区间直接回答 0。只推进到非平凡查询的最大 pre、最大 \(r\)； 没有查询的中间前缀仍推进端点，但不重建树状数组。某一行的树状数组只扫到 该行最大 \(r\)。若所有端点都变成 −1，说明已把相关 \(b\) 前缀完整匹配为子序列， 之后的查询直接返回区间长度，可以结束扫描。

设非平凡查询的最大前缀和右边界为 \(M\)、\(N\)，其不同前缀数为 \(K\)，总查询数为 \(Q\)。 在下标访问、相等比较均为 \(O(1)\) 时，时间上界为 \(O(MN + (KN+Q)\log(N+1) + M+N+Q)\)，空间为 \(O(M+N+Q)\)，包含前缀分桶和返回数组。 没有非平凡查询时为 \(O(Q)\)，不扫描字符。普通密集查询的复杂度仍可达 \(O(MN \log(N+1) + Q \log(N+1))\)；剪枝主要帮助稀疏查询和提前匹配完成的输入。

滚动哈希：指纹、共享幂表与最长匹配

rolling_hash<Symbol,Hash> 为静态序列保存前缀哈希，默认 Hash 是模 \(2^{61}-1\) 的 modint61。同一 Hash 类型的默认构造对象共享进程内随机基数和幂表； 显式传入基数时创建独立上下文，复制对象则共享原上下文、独立保存前缀数组。 基数在 Hash 中的值不能为 0、1、−1。构造与 build 接受 vector 或 string； 先转换到 Symbol，再把 char/signed char/unsigned char 规范为 \(0,\ldots,255\) 的字节值， 其他整数按模数归约。因此 rolling_hash<int>(string) 保留 char 转 int 后的符号， 若要统一处理字节，请用 rolling_hash<char> 或显式转换后的整数数组。

prod(l,r) / slice(l,r) 返回半开区间的 {h,len} 指纹，包含长度，所以空串与 单个 0 的指纹不同。concat(x,y) 对应 \(x\) 后接 \(y\)，公式是 \(h_{xy}=h_x B^{\lvert y\rvert}+h_y\)。 两个 token 必须来自相同 Hash 和基数；token 自身不记录基数。 same(a,l1,r1,b,l2,r2) 先检查兼容性和长度，再比较指纹。 哈希相同仍可能碰撞，不能作为确定性的字符串相等证明；整数相差模数时甚至 必然得到相同单元素指纹。对结果要求确定无误时，应使用直接比较或后缀数组等方法。

lcp(a,i,b,j) 求从 \(i\)、\(j\) 开始的后缀的最长公共前缀，允许下标等于序列长度。 lcs(a,i,b,j) 求分别以 \(i\)、\(j\) 结尾的最长公共后缀，端点 \(i\)、\(j\) 为包含端点； −1 表示空前缀。例如对 abracadabra，lcp(0,7) 和 lcs(3,10) 都是 4。 两者用哈希二分，判等也带有碰撞风险。还支持提供 prod 和 size() 或 \(n\) 的外部 哈希对象；长度须小于 INT_MAX，二分中点用差值计算，避免大下标相加溢出。

构建前按已知长度预留前缀容量，再逐项计算；build 可重建为空或 不同长度，复制对象的前缀值不受重建影响。常用定长数值 Hash 的构建时间 \(O(n)\)， 子串提取/判等 \(O(1)\)，LCP/LCS \(O(\log n)\)。concat 只有在右侧长度的幂已缓存时才是 \(O(1)\)； 从最大指数 \(p\) 补到 \(k\) 需 \(O(k-p)\) 摊还时间，单次扩容可能搬迁整个幂表。 前缀数组与幂表会保留容量，实际空间应按 \(O(C+P)\) 计算，其中 \(C\) 是本对象前缀容量， \(P\) 是其共享上下文的幂表容量，不能仅按重建后较短的序列长度估算。 token 拼接的总长度、前缀长度加一均须在 int 范围内。

Runs：最小周期与极大重复区间

runs(s) 接受 string 或字符/整数 vector，返回按 (period,left,right) 排序且去重的 三元组。每个 \([\mathrm{left},\mathrm{right})\) 至少容纳两个周期，period 是该区间的最小周期，且不能 保持此周期再向左或向右扩展一个字符。长度不必是周期的整数倍：abababa 的唯一 结果是 (2,0,7)；aaaa 只返回 (1,0,4)，不再枚举周期 2 或内部小区间。 空序列和单元素序列均返回空数组，输入长度须小于 INT_MAX。

实现对字符序及反向字符序各扫一次单调栈。弹出位置 \(j\)、遇到右边界 \(i\) 时， 两者之差 \(p\) 是候选 Lyndon 根的长度；此时已经得到的 LCP 可以直接用于周期向右 扩展，无须保存整张 Lyndon 边界数组再查询一次。再求向左匹配长度 left， 当 \(\mathrm{left}+\mathrm{LCP}\ge p\) 时，就得到至少两个周期的区间。

只保留落在 run 开头第一个周期内的根，即 \(\mathrm{left}<p\)。如果根之前紧接着相同的 长度 \(p\) 块，前一个根会给出同一个 run，可以提前跳过；例如 aaaa 只需最前面的 长度 1 根，后面的重复根不再各生成一份 (1,0,4)。首字符不等时 LCP 为 0， 前一个字符不等时左扩展为 0；周期大于总长度一半或左侧剩余长度不足的候选也可跳过。 扫描到位置 \(n\) 时清空单调栈，处理延伸到序列末尾的根。string 直接遍历原字符，不复制数组。

最长匹配和重复块判定仍使用滚动哈希，因此结果有碰撞风险，尤其整数按模数归约后 可能相同。这里要求字符/整数的相等和大小比较一致；不把哈希判等当作确定性证明。 时间上界仍为 \(O(n \log n)\)，工作数据和输出为 \(O(n)\)，另加默认哈希上下文保留的共享幂表。 字符比较、哈希算术按常数时间计；实现未构造 \(O(n \log n)\) 的后缀 RMQ 表。

后缀数组查询：区间搜索与重复构建

suffix_array_query(s) 保存字符串副本，build(s) 可以重新建立索引；长度须小于 INT_MAX。字符按 \(0,\ldots,255\) 的无符号字节顺序排列，支持 NUL 和高位字节，和 string_view::compare 的顺序一致，不依赖编译器的 char 符号设置。

longest_common_prefix(a,b) 返回两个非空后缀的最长公共前缀长度，要求 \(0\le a,b<\lvert s\rvert\)；相同位置返回剩余后缀长度。 interval(t) 返回匹配前缀 \(t\) 的后缀数组排名区间 \([l,r)\)。未命中时返回 \([p,p)\)，\(p\) 仍是字典序插入位置。空模式匹配全部 \(n\) 个非空后缀，不包括末尾的 空后缀；空文本返回 [0,0)。occurrences(t) 按文本位置升序返回起点， occurrences(t,false) 按后缀数组顺序返回。

例如 banana 的后缀数组为 [5,3,1,0,4,2]，模式 ana 的区间是 [1,3)， 两种出现位置结果分别为 [1,3] 和 [3,1]。左端点二分仍直接比较字符串； 一旦记住某个匹配后缀，右端点只需判断其他后缀与它的 LCP 是否至少为模式长度。 未命中时省去第二次二分，空模式直接返回整个区间。不引入完整的模式 LCP 搜索。

构建复用已有逆排名直接计算 Kasai LCP，写入稀疏表底层；重建时调整每层长度， 覆盖全部有效元素，避免旧 LCP 层残留。构建时间 \(O(n \log(n+1))\)，LCP 查询 \(O(1)\)， 非空模式区间查询 \(O(m \log(n+1))\)；空文本或空模式查询 \(O(1)\)。返回 \(z\) 个起点还需 \(O(z)\) 输出空间及 \(O(z)\) 时间，按文本位置排序时为 \(O(z \log(z+1))\) 时间。 容器可保留重建前的容量，整体保留空间上界按历史最大长度 \(N\) 计为 \(O(N \log(N+1))\)。

后缀自动机：状态、克隆与子串计数

suffix_automaton<sig> 在线接收编码在 \([0,\mathrm{sig})\) 的整数符号；默认 \(\mathrm{sig}=26\)。 字节输入应先转为 unsigned char，再交给 \(\mathrm{sig}=256\) 的实例。构造后只有根节点 0， lst=0，根的 lnk=-1、len=0；转移值 -1 表示不存在。 extend(c) 返回本次新增的前缀状态编号，并更新 lst；需要拆分状态时另外创建克隆。 每次最多增加两个状态，所有长度和节点编号须能用 int 表示。

同一状态代表结束位置集合相同的一组子串，长度连续地落在 [nd[nd[v].lnk].len+1, nd[v].len]。因此 count_substring_at(v) 返回这个 长度区间的大小；根返回 0。它不是出现次数：字符串 abb 中，b 对应两个 结束位置，但其状态只代表一个不同子串，计数仍为 1。 count_substring() 遍历全部状态，返回非空不同子串总数；abb 的结果为 5。

普通节点直接在 vector 中构造，转移表仍初始化为 -1。克隆直接复制被拆分节点的 转移和后缀链接，再修改最大长度，避免先清空转移表再整体覆盖。vector 扩容时 也允许这样复制自身已有元素；代码只保存节点编号，扩容后重新按编号访问。

get_tree() 返回从后缀链接父节点指向子节点的邻接表，各孩子按编号升序。 克隆可能成为更早节点的父亲，不能假设 lnk[v] < v；汇总出现次数等信息时， 应按 len 降序或对链接树做后序处理。实例可以复制后独立追加；已知最终长度 \(n\) 时， 调用方可以按内存预算用 nd.reserve(2*n) 减少扩容，接口不强制预分配。

\(n\) 次追加构建总时间 \(O(n \mathrm{sig})\)，固定字母表时为 \(O(n)\)；单次追加可能遍历很多链接， 扩容也可能搬移已有状态，不能把单次最坏时间当作 \(O(1)\)。\(m\) 个状态占 \(O(m \mathrm{sig})\) 空间， \(m\) 不超过 \(2n+1\)。单状态计数 \(O(1)\)，总计数与链接树构建 \(O(m)\)；返回的树另占 \(O(m)\) 空间。

通配符匹配：有界平方差与精确零值判定

wildcard_matching(s,t,wc='?') 返回所有匹配起点，按升序排列。\(s\) 和 \(t\) 两边的 wc 都能匹配任意一个字节；支持 NUL 和 \(128,\ldots,255\) 字节。空模式匹配 \(0,\ldots,n\) 共 \(n+1\) 个 边界，模式比文本长时返回空数组；输入视图可重叠，函数不修改输入。 长度 \(n\) 须小于 INT_MAX；非空且 \(m\le n\) 时仍要求 \(n+m-1 \le 2^{24}\)。

令非通配字符的值 \(x\) 为其无符号字节值加一，通配符的 \(x\) 为 0，另令 \(M\) 表示 该位置是否非通配。对齐处的三项卷积给出

\[ E=\sum_i\bigl(x_{s,i}^2M_{t,i}+M_{s,i}x_{t,i}^2-2x_{s,i}x_{t,i}\bigr). \]

两边均非通配时，每项是字节差的平方；有一边为通配时该项为 0。 所以总分 \(E\) 非负，且 \(E=0\) 恰好表示匹配。例如 a?c 与 abc 的总分为 0， 与 abd 的总分为 1；这里用到的是数值为零，不需要恢复每个 64 位卷积系数。

设所有非通配字节的最小、最大值为 \(\mathrm{low}\)、\(\mathrm{high}\)，两串的非通配字符数分别为 \(c_s\)、\(c_t\)。 任一对齐都满足 \(E\le\min(c_s,c_t)(\mathrm{high}-\mathrm{low})^2\le65025m\)。 先在模 2013265921 下判零；若上界小于该模数，或已没有候选，查询即结束。 否则再用模 167772161 过滤。上界远小于两模数之积，两个模下都为零只能是 \(E=0\)， 因此不会把模数回绕误当成匹配。上界为零时直接返回所有对齐。

每个模数对三对多项式分别做正变换，把三个频域乘积相加后只做一次逆变换， 即六次正变换加一次逆变换。逆变换的长度归一化可省略，因为变换长度在两个 素数模下都可逆，不影响零值判定。每轮只保留累加数组和当前两个输入数组， 两个模数依次处理；复用 ACL 的蝶形内核，不引入浮点 FFT 或随机参数。

当模式长度或候选起点数不超过 60 时直接逐字符比较，与 ACL 的小卷积阈值一致； 最多做 \(60n\) 次字符比较，仍为线性时间。其余情况总时间 \(O((n+m) \log(n+m))\)， 空间 \(O(n+m)\)，包括结果。空模式只需 \(O(n)\) 输出，模式过长时 \(O(1)\) 返回。

\(q\)-组合数：按逆序对给 01 串计权

普通组合数 \(\binom{n}{k}\) 统计在 \(n\) 个位置中选 \(k\) 个，有多少种选法。 把选中的位置写成 1，其余写成 0，就得到长 \(n\)、恰有 \(k\) 个 1 的所有 01 串。 \(q\)-组合数让每个串 \(s\) 贡献 \(q^{\operatorname{inv}(s)}\)，再把这些贡献相加； \(\operatorname{inv}(s)\) 是前面的 1 和后面的 0 组成的数对个数，不要求相邻。

例如 \(n=3\)、\(k=1\)：

01 串 逆序对数 贡献
001 0 \(1\)
010 1 \(q\)
100 2 \(q^{2}\)

所以 \(q\)-组合数为

\[ \begin{bmatrix}3\\1\end{bmatrix}_q=1+q+q^2. \]

当 \(q=1\) 时，每种选法的贡献都是 1， 就回到普通组合数 3；当 \(q=2\) 时，加权和是 7。 题目若要求固定 0、1 个数的串按逆序对数加权，便可直接套用。 例如

\[ \begin{bmatrix}4\\2\end{bmatrix}_q=1+q+2q^2+q^3+q^4, \]

\(q^2\) 的系数 2 表示有两个串 恰有两个逆序对；但当前模板只算给定 \(q\) 的值，不提供全部系数或指定逆序对数的方案数。

另一个用途是有限域上的子空间计数：当 \(q\) 是素数幂时， \(\begin{bmatrix}n\\k\end{bmatrix}_q\) 等于 \(q\) 元有限域上 \(n\) 维向量空间中 \(k\) 维线性子空间的数量。 例如二元域上三维空间有 7 个非零向量，每个一维子空间恰有一个非零向量， 因此有 \(\begin{bmatrix}3\\1\end{bmatrix}_2=7\) 个一维子空间。这里统计的是子空间， 同一个子空间换一组基不会重复计数。\(q\) 为素数幂是这一解释的条件； 前面的 01 串加权和对任意非负整数 \(q\) 都有意义。

q_binomial_prime_table(queries,p,q) 中，\(q\) 是权重参数，\(p\) 是答案取模的素数。 先给出全部 (n,k) 询问用于预处理，再用 choose(n,k) 取值：

#include "noya/math/q_binomial_prime.hpp"
#include <iostream>
#include <utility>
#include <vector>

int main() {
  std::vector<std::pair<int, int>> queries{{3, 1}, {4, 2}};
  noya::q_binomial_prime_table table(queries, 101, 2);
  std::cout << table.choose(3, 1) << '\n'; // 7
  std::cout << table.choose(4, 2) << '\n'; // 35
}

本实现要求 \(2\le p\le\mathrm{INT\_MAX}\) 且 \(p\) 为素数，传给构造或 build 的询问满足 \(0\le n,k<p\)；后续查询的 \(n\) 不超过预处理时的最大 \(n\)。 choose(n,k) 在 \(k<0\) 或 \(k>n\) 时返回 0。\(q\) 会先对 \(p\) 取模； \(q=0\) 时合法 \(k\) 的答案为 1，\(q=1\) 时就是普通组合数。

实现使用 \(q\)-Lucas 分解来处理 \(1-q^{i}\) 在模 \(p\) 下变成零、无法直接求逆的情况， 这不表示本模板支持任意大的 \(n\)；仍须满足上述范围。若只是普通组合数， 使用 binomial 或 prime_binomial_table 即可。

位运算卷积

noya/math/convolution.hpp 的 AND / OR / XOR 接口仍接收两个等长、非空、 长度为 2 的幂的 vector<T>，返回卷积结果。按值传参保留调用方的数组； 不再使用输入时可以传入 std::move(a), std::move(b)，省去输入复制。 XOR 要求 T(N).inv() 存在，即长度 \(N\) 在系数环中可逆。 AND、OR 和子集卷积仍支持普通整数及偶数模数；整数中间结果须不溢出。

内核把长度分派到编译期常量，递归处理连续区间；ACL 静态模整数使用便于向量化的模加减。 编译器可对独立的连续运算进行向量化。OR 直接执行自身的变换，无需数组翻转。 子集卷积也复用该变换。奇数模数的 ACL 静态模整数自动采用简单的 XOR 压缩： 按秩分层时省略 mask 最低位，使每层长度从 \(N\) 变为 \(N/2\)；秩与其余位的奇偶性 可以恢复省略位，取目标秩时排除有交集的项。其他系数类型仍用不需要除法的 OR/zeta 变换。复杂度仍为 \(O(N \log^{2}N)\) 时间、\(O(N \log N)\) 空间；只压缩这一位， 不引入分块参数或专用小多项式乘法。

头文件不设置全局优化或 CPU 指令集选项。正常使用 -O2；追求性能时可实测 -O3。仅在目标 x86 CPU 支持 AVX2 时加 -mavx2，ARM 不需要这个选项。 编译器、目标指令集和系数类型都会影响实际向量化情况。 读取大量数据前仍需调用 noya::fast_io()，或手动关闭 iostream 同步并解除 cin 绑定。

GCD / LCM 卷积使用按质数分解的整除变换，时间为 \(O(N \log \log N)\)、空间为 \(O(N)\)。两个输入仍按 const vector<T>& 传入；下标 0 被忽略，输出下标 0 为零。 LCM 只返回下标不超过 \(N\) 的部分。变换不需要逆元，普通整数、偶数或合数模数 也适用；整数的中间结果须能在所选类型中表示。

几何覆盖

二维模块包括基本谓词、凸包、半平面交、最近/最远点对、最小覆盖圆、圆交点与切线、 Minkowski 和、矩形面积并、凸层、三角形计数和欧氏最小生成树。 补充的常用接口如下：

头文件 接口与复杂度
geometry_distance.hpp 投影、对称点、点到直线/线段、线段间距离，\(O(1)\)
convex_polygon.hpp \(O(n)\) 规范化，\(O(\log n)\) 点定位；\(O(n)\) 裁剪和重心
circle_polygon_area.hpp 两圆交面积 \(O(1)\)，圆与多边形交面积 \(O(n)\)
geometry_3d.hpp 三维向量、混合积、点线面距离、平面投影、线面交、四面体体积，\(O(1)\)

点定位沿用 -1 外部、0 边界、1 内部。直线和三维平面的退化结果使用 std::optional；零长线段按点处理；零面积多边形没有面积重心。 point<T> 的整数点积、叉积及方向判断在 T 内计算，调用者须保证中间结果不溢出， 必要时用 point<__int128>。浮点距离和面积接口使用 long double；容差含义及输入 前置条件以各函数注释为准，并非任意量级下的精确几何。

展开器

Python/Sublime 与 VS Code 实现使用同一组语义测试：

  • 支持单行字面量 quoted include、子目录、相对依赖和 #pragma once。
  • 提交输出删除头文件宏守卫和 #pragma once，并对受保护的重复依赖去重。
  • 默认保留 noya/utility/debug.hpp 的 include 及其 local 条件，不展开调试实现和依赖。 如需展开，Python 配置设 "excluded_headers": []，VS Code 设 icpcBookAutoExpand.excludedHeaders 为 []。
  • 保留 #if defined(local) 等功能条件；跨条件分支的重复依赖按实际包含条件处理，不生成头文件守卫。
  • 系统 include 保持原位置；条件分支、宏开关、重复无守卫包含和 #undef 后重包含交给编译器处理。
  • 有守卫的循环依赖可展开；活动的无守卫循环产生编译错误，避免无限递归。

宏生成的 include 和系统头不进行本地展开。Python 配置中的相对库路径按配置文件目录解析， 不依赖当前终端目录。VS Code 多选复制按文档换行风格连接。 上面的多选行为仅用于显式展开命令；普通 Cmd/Ctrl+C 与 Sublime 适配层一致， 仅展开单个非空 C++ 选区中的真实库 include。空选区、多选、普通文本、注释和字符串 使用原生复制；展开保留选区空行、换行风格和末尾换行。 若控制重复包含的条件宏中途变化，且清理守卫需要其旧值，展开会报错，普通复制回退为原生复制。

伴随矩阵：前向消元与按秩恢复

adjugate_matrix(mat) 返回方阵的伴随矩阵，即余子式矩阵的转置；元素类型须为域， 支持精确判零和非零元素求逆。时间 \(O(n^{3})\)，额外空间 \(O(n^{2})\)。输入按值传入， 可移动传参以省去调用处复制；空矩阵返回空矩阵，\(1\times 1\) 矩阵（包括零矩阵）返回 [1]。

前向消元只消去主元下方的元素，记录行变换矩阵 \(E\)，使 \(EA=U\)；主元归一化为 1。 令 \(d\) 为主元值之积并计入换行符号，则 \(\det(E)=\frac1d\)，这里 \(d\) 在奇异情形也非零， 但不等于奇异矩阵 \(A\) 的行列式。

  • 满秩时，\(\det(A)=d\)，回代解 \(UX=E\) 得到 \(X=A^{-1}\)，最后返回 \(dX\)。 回代只更新 \(E\) 的工作区，不必继续把 \(U\) 的主元上方消成零；结果也直接复用这块工作区。
  • 秩为 \(n-1\) 时，设唯一自由列为 \(f\)，令右零向量 \(v\) 的 \(v_f=1\) 并从后向前解 \(Uv=0\)。 \(U\) 的末行全零，\(E\) 的末行 \(w\) 因而满足 \(wA=0\)。删除 \(U\) 的末行和第 \(f\) 列所得子式 为单位上三角阵，故 \(\operatorname{adj}(U)=(-1)^{n-1+f}v e_{\mathrm{last}}^{\mathsf T}\)；由 \(\operatorname{adj}(A)=d\operatorname{adj}(U)E\) 得到 \(\operatorname{adj}(A)=d(-1)^{n-1+f}vw\)。
  • 秩不超过 \(n-2\) 时，每个 (\(n-1\)) 阶子式都是零，直接返回零矩阵。

例如 \(A=\begin{pmatrix}1&2\\2&4\end{pmatrix}\)，前向消元得到 \(U=\begin{pmatrix}1&2\\0&0\end{pmatrix}\)、 \(E=\begin{pmatrix}1&0\\-2&1\end{pmatrix}\)，右零向量为 [-2,1]，\(E\) 末行为 [-2,1]，\(d=1\)， 所以伴随矩阵是外积 [[4,-2],[-2,1]]。仅检查 \(A\operatorname{adj}(A)=0\) 无法验证奇异情形 的结果：错误的全零矩阵也满足它，因此测试另用完整余子式和初等变换构造的答案。

批量求逆：四条独立前缀积链

batch_inverse(vs) 返回各元素的逆，输入元素须为域中的非零元素，长度不超过 INT_MAX。空输入返回空数组，不做除法；非空输入只做一次除法。时间为 \(O(n)\) 次 域运算，结果占 \(O(n)\) 空间，结果之外只需常数空间。输入保持不变。

将下标按模 4 的余数分成四条链，每条链分别求前缀积，并把“不含自身”的前缀积 放进结果数组。四条链互不依赖，编译器可以交错安排它们的乘法，不必等待一个 长前缀积反复完成。两处 GCC unroll 4 仅为循环展开提示，算法不依赖某种 SIMD 指令。

得到四个链积后，再用普通批量求逆法反转这四个数：保存它们的前缀积，只对总积 做一次除法，再从后往前恢复四个逆。最后倒序扫描原数组，每条链用自己的逆积 恢复当前元素的逆，再乘回当前元素。不存在元素的链，其积为 1，同样适用。

例如 [a,b,c,d,e] 的四条链是 [a,e]、[b]、[c]、[d]，保存的前缀为 [1,1,1,1,a]。拿到 \((ae)^{-1}\) 后，\(e\) 的答案是 \(a\cdot (ae)^{-1}=e^{-1}\)；再将链的 逆积乘上 \(e\)，得到 \(a^{-1}\)。其余三条链也分别恢复 \(b\)、\(c\)、\(d\) 的逆。

非空输入一共做 \(3n+9\) 次乘法。断言模式逐个检查非零前提，不支持 直接传入零；允许零的调用方应像 polynomial_special_points 一样先筛出非零项。

任意进制大整数加法：直接回填与统一数字解析

add_big_integers(a,b,base=10,cap=false) 接受 \(2,\ldots,36\) 进制的带符号整数字符串； 可带 + 或 -、前导零以及混合大小写字母。输入须至少有一位合法数字，字母的 数值不随大小写变化。输出由 cap 决定字母大小写，去除前导零和负零。输入视图 可以相同或重叠，函数不修改输入。时间 \(O(\lvert a\rvert+\lvert b\rvert)\)，空间 \(O\bigl(\max(\lvert a\rvert,\lvert b\rvert)\bigr)\)。

先解析符号并比较绝对值。同号时相加；异号时用较大的绝对值减去 较小的绝对值，并采用较大者的符号；绝对值相等直接返回 "0"。

数字解析使用编译期生成的 256 字节表，数字和大小写字母映射到 \(0,\ldots,35\)，其他 字节映射到 -1。索引用 unsigned char 转换，避免 signed char 的负下标。 断言模式仍验证进制、非空输入及每一位的范围。共享的解析助手也供大整数乘法使用。

加法预先建立 \(\max(\lvert a\rvert,\lvert b\rvert)\) 位结果，从末尾向前写入。每次两位数字与进位之和 满足 \(0\le v<2\mathrm{base}\)，所以新进位等于 v >= base，输出位为 v - carry*base，不需要整除和取模。最终仍有进位时在开头补 1。

减法同样从结果末尾回填，v = a_digit - borrow - b_digit 满足 \(-\mathrm{base}\le v<\mathrm{base}\)，新借位为 v < 0，输出位为 v + borrow*base。 最后删除前导零。例如 1000 - 1 的借位依次传播，得到 0999，再规范化成 999。两种运算都省去逐位 push_back 和最后的反转；负号仍统一由外层处理。

保留以较大绝对值减较小绝对值的前提，确保最终借位为零。查表不会放宽输入域： 非法字节仍返回 -1；开启断言时，非法进制、只有符号、空输入或超出当前进制的数字仍触发断言。

十进制大整数除法：原地长除法与 Newton 倒数

divide_big_integers(a,b) 返回十进制商和余数，主要用于非负整数，除数必须非零。 输入可以含前导零，输出去掉前导零；输入视图可以相同或重叠，函数不修改输入。 带符号除法向零取整，非零余数与被除数同号，不产生负零。 输入须为有效的十进制整数，不新增加号或其他格式的解析。

内部以 \(10^{9}\) 为一个数位。除数不超过 64 个数位，或被除数与除数的长度差不超过 64 时使用长除法；更大的输入用 Newton 倍增求定点倒数，再乘回并修正商。 乘法的较短操作数不超过 128 个数位时仍用普通乘法，否则用三模 NTT。 \(n\) 为输入的最大十进制位数，总时间 \(O(n \log n)\)， 空间 \(O(n)\)；短除数/短商的分支受固定阈值限制。

长除法先将两数同时乘 D/(b.back()+1)，使除数最高位至少为 \(D/2\)。 随后用当前余数窗口的最高两位估计商位，并限制在 \(0,\ldots,D-1\)。估计值不会偏小， 至多偏大 2；直接在被除数数组的当前窗口减去“除数 × 商位”。若出现最高位 借位，就将商减 1 并加回一次除数，直到不再借位。处理完后，低位窗口就是 归一化的余数，除掉归一化因子即可。

例如暂以 10 为基数计算 \(398/59\)，最高两位估出 \(\lfloor39/5\rfloor=7\)，但 \(398-7\cdot59=-15\)；将商减成 6 并加回 59，得到余数 44。

解析直接读取 string_view，并去掉高位零。例如 42 / 0000000000000000001 得到商 42、余数 0。

任意进制大整数乘法：延迟进位与精确整数卷积

multiply_big_integers(a,b,base=10,cap=false) 支持 \(2,\ldots,36\) 进制、正负号、前导零、 混合大小写输入和 cap 指定的输出大小写，结果不带前导零或负零。输入视图可以 相同或重叠，函数不修改输入；解析沿用大整数加法的约定。

将若干字符打包成一个数位，选择不超过 10,000 的最大 base 次幂 \(B\) 作为基数。 若较短操作数不超过 32 个数位，先用两个循环累加所有 a[i]*b[j] 到 c[i+j]， 再从低位到高位统一进位。每个原始系数最多含 32 个乘积，小于 \(32\cdot B^{2}\)，无需 在每一对数位相乘时做除法，也不需要 128 位整数。比如以 10 为基数， \(99\cdot99\) 先得到低位在前的 [81,162,81]，一次进位后得到 [1,0,8,9]，即 9801。

较长输入复用 ACL 的 convolution_ll，直接得到精确整数系数，再做一次进位。 此分支沿用卷积结果长度不超过 \(2^{24}\) 个打包数位的限制。此时较短输入至多 \(2^{23}\) 个数位，所以每个系数至多 \(2^{23}\cdot (10000-1)^{2} < 2^{50}\)，能够用有符号 64 位整数 精确还原。前一位带来的进位不超过最大系数除以 \(B-1\)，系数加进位仍小于 \(2^{51}\)， 因此后续归一化同样只需 64 位。省去了任意模数卷积的额外取模与上界扫描。

设 \(n\) 为较长输入的字符数，时间 \(O(n \log n)\)、空间 \(O(n)\)。

素数模组合数：一次求逆，倒推逆阶乘

binom<T> 保留公开的 fac、ifc 数组以及 prepare、fact、ifact、C 接口。 T 需要从整数构造、复制、相乘和提供 inv()；不额外要求默认构造函数。 模数在表的生命周期内保持不变，所有预处理到的阶乘都必须可逆。通常令模数 为素数 \(p\)，并使用 \(0,\ldots,p-1\) 范围内的阶乘下标。合数模的通用组合数应使用 binomial_mod_table，不能直接对含有模数因子的阶乘求逆。

扩展到 \(n\) 时，先只补齐新增的阶乘，然后计算一次 ifc[n]=fac[n].inv()， 再倒推 ifc[i-1]=ifc[i]*i，直到新增区间的开头。因为 \(i!=(i-1)!\,i\)，所以 \(\frac1{(i-1)!}=\frac{i}{i!}\)。例如已得到 \(\frac1{5!}\)，乘 5 就是 \(\frac1{4!}\)，再乘 4 就是 \(\frac1{3!}\)。已有前缀保持不变；没有扩展或只初始化 \(0!\) 时 不求逆。

设一次求逆代价为 \(I\)，从空表准备 \(n\) 的时间为 \(O(n+I)\)，空间 \(O(n)\)；扩展已有表只 计算新增部分，再做一次求逆；向量扩容可能复制旧元素，存储增长成本按摊还计。fact、ifact 和有效的 C 会自动按约两倍的 目标下标扩容，准备到最大下标 \(n\) 的总时间为 \(O(n+I \log n)\)，已缓存查询为 \(O(1)\)。 C(n,m) 先用 fact(n) 确保整个范围已准备，再直接读取两个逆阶乘，避免三次 分别检查和潜在的重复扩容。已缓存的阶乘查询仍在外层快速返回。 显式逐个调用 prepare(i) 仍会每次求逆；能确定上界时应一次 prepare(max_n)。

若 T 提供 T::mod()，自动扩容不会超过模数减 1，修复模 7 时查询 \(6!\) 却先 扩到 12、碰到不可逆 \(7!\) 的问题。没有 mod() 的自定义类型仍可使用，调用者 须保证自动扩展范围内的阶乘都可逆。阶乘查询下标必须非负且小于 INT_MAX； 对素数模还须小于 \(p\)。无效的组合数参数仍返回 0，包括 \(m<0\)、\(m>n\) 和 \(n<0\)。

默认构造仍保留空数组；第一次准备时补上 fac[0]=ifc[0]=1。重复准备更小范围 不缩表，复制后可以独立扩容，同时清空两个数组后可以重新准备。

任意模组合数：拆质数幂，合并分母求逆

binomial_mod(n,k,m) 支持正的 64 位模数，适合 \(\min(k,n-k)\) 较小的单次查询。 binomial_mod_table(m) 支持正的 32 位固定模数，先为每个质数幂 \(q=p^{e}\) 建立长度 \(q+1\) 的前缀积表，供多次查询使用。两者都接受 64 位 \(n\)、\(k\)，\(k>n\) 返回 0；\(m=1\) 返回 0。表的大小取决于质数幂本身：大素数模数仍会需要很大的 预处理时间和空间，不应仅凭它能放进 uint32_t 就直接建表。

合数模不能直接把分母阶乘求逆。例如 \(\binom{10}4=210\)，模 72 的答案是 66， 但 \(4!=24\) 在模 72 下没有逆元。先拆成模 8 和模 9：分别从分子、分母剥去 2 或 3 的因子，记下剩余指数；剩下的单位部分才有逆元。两个答案分别是 2 和 3，再由 CRT 合并成 66。单次计算把所有剥去质因子的分母先相乘，每个 质数幂只求一次逆；最后乘回质因子的幂。长乘积先检查答案是否必为 0。

固定模数表把 \(n!\)、\(k!\)、(\(n-k\))! 的单位部分和指数放在同一次逐层除 \(p\) 的循环中 计算。一整块单位的乘积只能是 ±1，可累计块数的奇偶性后统一处理；模 8、16 等情形的块乘积是 +1，不能一律当作 -1。每个质数幂的查询只求一次分母逆， CRT 系数则在构造时缓存。前缀表仍只保存一份 uint32_t 数组，不另存逆前缀。

令 \(F(m)\) 为分解模数的代价，\(K=\min(k,n-k)\)。 下面的求和遍历 \(m\) 的各个最大素数幂因子 \(p^e\parallel m\)， \(\omega(m)\) 表示不同质因子的个数。固定模数表的复杂度为

\[ \begin{aligned} T_{\mathrm{build}}&=F(m)+O\left(\sum_{p^e\parallel m}p^e\right),\\ T_{\mathrm{query}}&=O\left(\sum_{p^e\parallel m}\bigl(\log_p(n+1)+\log(p^e)\bigr)\right),\\ S&=O\left(\sum_{p^e\parallel m}p^e+\log m\right). \end{aligned} \]

查询时间包含扩欧求逆。单次接口的时间为

\[ F(m)+O\left(K\omega(m)+\sum_{p^e\parallel m}\bigl(\log_p(n+1)+\log(p^e)\bigr)\right), \]

辅助空间为 \(O(\log m)\)。 单次接口的 64 位模乘使用 128 位中间值；表内模数是 32 位，其余数乘积可安全 放在 64 位中。分解模数仍沿用 factorize，小 \(K\) 的总时间可能主要花在这里。

二元形式幂级数：沿一个方向扩展矩形

bivariate_convolution_truncated(a,b,n,m) 返回乘积在 \(x^{n},y^{m}\) 截断下的 \(n\times m\) 系数矩阵；不足的部分补 0。\(n\)、\(m\) 为 0 或任一输入为空时返回空矩阵， 其余输入须为非空矩形。bivariate_fps_inverse(f) 返回同尺寸的逆级数， 要求 \(f\) 非空且常数项非零。使用 ACL 的素数模静态模整数；打包卷积长度须满足其 整数索引与模数的 NTT 长度限制，通常选用 998244353 等支持 NTT 的素数。

乘法把 \(x^{i} y^{j}\) 放在下标 \(iW+j\)，\(W\) 取两输入有效宽度之和减一。 例如宽度分别为 3 和 4，\(W=6\)，\(y\) 次数最高为 5，不会进位到下一个 \(x\) 次数。 卷积结束后再取所需矩形。小操作数不超过 16 个有效系数时直接做截断乘法； 其余情况将临时打包数组移动给 ACL 卷积，省去两份输入复制。

求逆先求出 \(x^{0}\) 行，也就是 \(y\) 上的一元逆，再扩展 \(x\) 的精度。例如 \(f=1-x-y\) 在 \(2\times 3\) 矩形中的逆是 [[1,1,1],[1,2,3]]：先得到第一行 g=[1,1,1]，\(f\cdot g\) 新增的 \(x^{1}\) 行是 [-1,-1,-1]，再乘 \(g\) 并取负，得到 第二行 [1,2,3]。

一般地，已知 \(g\) 在 \(x<d\) 内正确，新精度 \(d+t\) 满足 \(t\le d\)，则 \(f\cdot g=1+x^{d} E\)。新增加的部分是 \(-x^d(gE\bmod x^t)\)；误差平方含 \(x^{2d}\)， 在新精度内为 0。因此只需提取高 \(t\) 行的误差，并计算 \(t\) 行修正。初始化 \(y\) 方向时使用相同公式。递归对目标尺寸取上半，展开后按这些尺寸更新，避免 1、2、4、…、256、257 这种最后只补一行却重新做大卷积的情况。

\(n\times m\) 求逆仍为 \(O(nm \log(nm+1))\) 时间、\(O(nm)\) 辅助空间；递归深度为 \(O(\log n+\log m)\)。矩形乘法另计 \(n\times m\) 输出初始化， 其时间为 \(O(nm+L \log(L+1))\)、空间为 \(O(nm+L)\)，\(L\) 是有效输入的打包乘积长度。 输入数组通过 const 引用传入，乘法也支持 \(a\)、\(b\) 引用同一个矩阵。

特征多项式：保持相似变换，跳过零贡献

characteristic_polynomial(a) 返回 \(\det(xI-a)\) 的系数，按常数项到最高次项 排列；\(n\times n\) 输入得到 \(n+1\) 项，最高次系数为 1，空矩阵返回 {1}。输入须为 方阵，T 的运算须构成域，例如素数模整数；算法只对已经选出的非零主元求逆， 支持模数为 2、3 等小特征的域。按值接收矩阵，因此普通左值调用保留原矩阵， 也可以用 std::move(a) 交出已有副本。

上、下三角矩阵直接计算 \(\prod_{i=0}^{n-1}(x-a_{ii})\)，耗时 \(O(n^{2})\)。一般矩阵先通过 相似变换化为上 Hessenberg 形式，也就是主对角线下方只保留一条次对角线。 例如消去第 \(c\) 列、主元行为 \(p=c+1\) 时，令 \(t=\frac{a_{r,c}}{a_{p,c}}\)：除了 row[r] -= t*row[p]，还必须做 column[p] += t*column[r]。 这两个操作配对才是相似变换，才能保持特征多项式；只做普通行消元不够。

同一列的消元系数不受右侧列更新影响，可先完成各行消元，再合并列更新。 实现只记录非零系数，并按矩阵的每一行依次读取这些列，减少反复跨行访问。

设 \(P_s\) 是左上 \(s\times s\) 子矩阵的特征多项式。Hessenberg 形式下，先计算 \((x-a_{s-1,s-1})P_{s-1}\)，再减去沿次对角线连到第 \(s\) 列的修正项。 例如 \(2\times 2\) 矩阵得到 \((x-a_{00})(x-a_{11})-a_{01}a_{10}\)。沿链的乘积一旦为 0， 更长的链也都为 0，可以停止；对应的上方元素为 0 时也直接跳过该项。 这尤其适合分块矩阵、伴随矩阵和已经接近三角形的输入。

一般情况仍为 \(O(n^{3})\) 次域运算、\(O(n^{2})\) 空间；三角矩阵分支为 \(O(n^{2})\) 时间。 T 需要默认构造、整数构造、复制、相等比较、乘除和复合赋值接口， 未额外要求一元负号或二元加减运算符。

组合序列：稀疏分母、平移复用与固定列截断

combinatorial_sequences.hpp 返回 Bell 数、Bernoulli 数、划分数及两类 Stirling 数的整行或固定列。整行和普通序列的结果包含下标 0 到 \(n\)；固定列返回 第 \(k\) 行到第 \(n\) 行，长度为 \(n-k+1\)。第一类 Stirling 数带符号，Bernoulli 数采用 \(B_1=-\frac12\)。要求 \(n\ge 0\)、固定列 \(0\le k\le n\)；使用 ACL 支持的素数模静态模整数和 卷积长度。含阶乘逆元的公式要求 \(n<\mathrm{mod}\)，Bernoulli 数要求 \(n+1<\mathrm{mod}\)。

阶乘与逆阶乘只求一次逆，返回时移动两个数组。Bell 数直接把逆阶乘数组的 常数项置零后求指数；Bernoulli 数把它左移一项作为分母，两者都复用临时存储。

划分数生成函数为

\[ P(x)=\prod_{j\ge1}\frac1{1-x^j} =\frac1{1-x-x^2+x^5+x^7-x^{12}-x^{15}+\cdots}. \]

五边形数定理说明分母在广义五边形数 \(\frac{k(3k\pm1)}2\) 处填入 \((-1)^k\)。 建立这个稀疏分母后只需一次 FPS 求逆，省去逐项求逆、约数和与 FPS 指数。 例如前六项划分数为 1,1,2,3,5,7。

第一类整行是 \(\prod_{i=0}^{n-1}(x-i)\)。连续乘积的一半可以平移得到另一半： 例如 \(a=x(x-1)\)，\(a(x-2)=(x-2)(x-3)\)，相乘就得到前四个因子的乘积。 一般区间 \([l,r)\) 取 \(h=\left\lfloor\frac{r-l}{2}\right\rfloor\)，只递归求前 \(h\) 个因子，再做 -h 的 Taylor shift；奇数长度最后补一个因子。长度不超过 60 时直接乘线性因子， 与 ACL 的朴素卷积分界一致。保持任意起点 \(l\) 的语义，递归深度 \(O(\log n)\)， 乘积的多项式工作量从 \(O(M(n) \log n)\) 降至 \(O(M(n))\)，另计逐层求逆的代价。

固定列先去掉已知的 \(x^{k}\)，只计算 \(n-k+1\) 项：第一类对 \(\frac{\log(1+x)}x\) 求 \(k\) 次幂， 第二类对 \(\frac{e^x-1}x\) 求 \(k\) 次幂。两者常数项都是 1，因此直接使用 \(\exp(k\log f)\)，结果第 \(j\) 项乘 \(\frac{(j+k)!}{k!}\)。第一类的系数 \(\frac1{j+1}\) 由 fac[j]*ifc[j+1] 得到。\(k=0\)、\(k=1\)、\(k=n\) 直接返回已知列；第二类整行仍采用 逐项快速幂和一次卷积，保留较短的实现。

统一保守时间上界为 \(O(M(n) \log n+n \log \mathrm{mod})\)，空间 \(O(n)\)；阶乘辅助函数 为 \(O(n+\log \mathrm{mod})\)，连续乘积为 \(O(M(n)+\log n \log \mathrm{mod})\)。

\(\mathrm{GF}(2^{64})\) 卷积：固定多项式约减

gf2_64 用 64 位整数的各位表示二元多项式，模多项式为 \(x^{64}+x^{4}+x^{3}+x+1\)。加法和减法均为异或，乘法先计算无进位乘积再约减； inverse() 要求元素非零。convolution_f2_64(a,b) 返回这些域元素的卷积， 任一输入为空就直接返回空数组，两个输入可以引用同一数组。

设无进位乘积为 \(L+x^{64}H\)。由 \(x^{64}=1+x+x^{3}+x^{4}\)，第一次折回得到 L ^ H ^ (H<<1) ^ (H<<3) ^ (H<<4)。超出 64 位的部分是 overflow=(H>>63)^(H>>61)^(H>>60)，至多 4 位，再乘同一个固定多项式 折回一次即可，结果最高不超过第 7 位，不会继续溢出。 因此只需要一次通用无进位乘法，其余都用无符号移位和异或完成。 例如 \(x^{63}\cdot x=x^{64}\) 约减后是 0x1b。

按编译目标使用 x86 的 PCLMUL、ARM 的 PMULL 或软件无进位乘法。

卷积使用加性 FFT、朴素乘法分支及共享的基缓存。每次递归中的 Taylor 变换需要 \(O(N \log N)\) 次异或，递归关系为

\[ T(N)=2T(N/2)+O(N\log N), \]

所以当前实现总时间为 \(O(N \log^{2}N)\)、空间 \(O(N)\)，\(N\) 是卷积长度补到的二次幂。 共享缓存用于串行调用。

大长度卷积：短边直接相乘，分块结果最后统一缩放

convolution_large(a,b,ntt) 返回普通多项式乘积，任一输入为空就返回空数组； 输入保持不变，也允许 \(a\)、\(b\) 引用同一个数组。Mint 使用 ACL 支持的素数模静态 模整数，ntt 是该模数支持的不小于 2 的二次幂，输入、输出长度及整数下标运算 须能用 int 表示。默认 \(\mathrm{ntt}=2^{23}\)，适用于 998244353；小模数须显式传入它支持的 长度，例如模 17 传 16。输出长度可以超过单次 NTT 的上限。

结果能装进一次变换时，继续调用 ACL 卷积。超过上限后，如果短边不超过 32， 直接朴素相乘。例如一个常数乘上超长多项式，本来只需逐项乘常数，不必建立 多块频域数组。这个分支沿用 ACL 的朴素乘法，不改共享的 ACL 源码。

其他情况仍按 \(\mathrm{bs}=\mathrm{ntt}/2\) 分块，各块只做一次正变换。设 \(a\) 的第 \(i\) 块、\(b\) 的 第 \(j\) 块分别为 \(A_i\)、\(B_j\)，它们的乘积从 \((i+j)\mathrm{bs}\) 开始，因此 \(i+j\) 相同的 块对可以先在频域相加，最后统一逆变换，再与相邻结果重叠相加。 例如 \(\mathrm{bs}=4\) 时，\(A_0B_1\) 和 \(A_1B_0\) 都从下标 4 开始；\(A_1B_1\) 则从下标 8 开始。

每组一定有至少一对块，累加数组直接用第一对的乘积初始化，省去清零及第一次 模加。各块的数组在使用时单独分配，不再先建立一个长度 ntt 的临时零向量再复制。 ACL 的逆蝶形没有除以 ntt；由于模数域中乘法对加法分配，可以等所有重叠结果 加完后，再把最终输出统一乘 \(\mathrm{ntt}^{-1}\)，避免交叠区重复缩放。

时间 \(O((n+m)\log L+nm/L)\)、空间 \(O(n+m+L)\)，\(L=\mathrm{ntt}\)。

任意模卷积：直接 NTT 与简化 CRT 重构

convolution_mod(a,b,mod) 返回非负剩余的普通卷积，结果仍是 uint64_t 数组。要求 \(\mathrm{mod}\ge 1\)、每个输入值小于 mod、输出长度不超过 \(2^{24}\)，并满足保守界 \(\min(n,m)\max(a)\max(b)<P\)，其中 \(P=167772161\cdot469762049\cdot1224736769\)。 任一输入为空时返回空数组；输入不被修改，也允许两参数引用同一数组。 支持 64 位目标模数不等于支持任意大小的整数卷积系数，使用前须检查这个界。

先扫描输入的最大值；如果任一数组全零，直接返回对应长度的零数组，也覆盖 \(\mathrm{mod}=1\) 的合法输入。模 998244353 且输出长度不超过 \(2^{23}\) 时，直接调用一次 ACL 卷积；超过 \(2^{23}\) 仍回退到三模数算法。三个 CRT 素数也可直接使用各自的 NTT。 其余模数在短边不超过 16 时使用朴素乘法，避免启动三个卷积。

一般情况仍使用三个素数。令 \(p_{1}\)、\(p_{2}\)、\(p_{3}\) 为上述素数，\(r_{1}\)、\(r_{2}\)、\(r_{3}\) 为同一系数 在三个模数下的余数。按顺序恢复

\[ \begin{aligned} x_2&=(r_2-r_1)p_1^{-1}\bmod p_2,\\ x_{12}&=r_1+p_1x_2,\\ x_3&=(r_3-x_{12})(p_1p_2)^{-1}\bmod p_3. \end{aligned} \]

于是完整系数是 \(x_{12}+p_1p_2x_3\)，最后对目标 mod 取模一次即可。 例如小素数 3、5、7 下，83 的余数是 2、3、6：先恢复 8，再加 \(15\times 5\) 得到 83。

实际素数下 \(x_{12}\) 不超过 57 位，前两步乘积都能放进 uint64_t；完整系数 不足 87 位，最后使用 unsigned __int128。模逆在编译期计算，传入 ACL 的 临时向量用移动传参；已经约减的值用 mint::raw，避免重复处理。 系数界断言改写为 \(\max(a)\max(b)\le\frac{P-1}{\min(n,m)}\)，防止长度乘积先溢出 128 位而漏报非法输入。这修正的是前置条件检查，不扩大支持的系数范围。

结果长度为 \(N\) 时，时间 \(O(N \log N)\)、空间 \(O(N)\)，短边分支为 \(O(nm)\)。

模 \(2^{64}\) 卷积：五模数重构与原生无符号乘法

convolution_mod_2_64(a,b) 返回 uint64_t 系数的普通卷积，结果自然对 \(2^{64}\) 取模。输入可以使用完整的 64 位范围，短边长度不超过 \(2^{19}\)，输出长度不超过 \(2^{22}\)。空输入返回空数组；输入不被修改，也允许 \(a\)、\(b\) 引用同一数组。 这与 \(\mathrm{GF}(2^{64})\) 卷积不同：这里的加法、乘法是整数运算后截取低 64 位。

任一数组全零时直接返回零数组。短边不超过 60 时直接相乘，使用无符号整数的 溢出规则完成模运算，省去五个素数卷积。其余情况使用五模数 NTT。 五个素数的乘积超过 \(2^{149}\)，而允许的最大整数系数小于 \(2^{147}\)，因此能唯一恢复 约减前的非负系数。输出长度的限制来自五个素数共同支持的 NTT 长度。

Garner 算法把整数系数写成 \(d_0+p_0d_1+p_0p_1d_2+\cdots\)。恢复第 \(k\) 位时， 先把已有位组成的前缀在 \(p_k\) 下求值，再减去这个前缀，乘以前面素数乘积的 逆元。例如前缀 \(d_0+p_0d_1+p_0p_1d_2\) 可写成 \((d_2p_1+d_1)p_0+d_0\)，从高位向低位计算就不用反复构造素数乘积。

每个素数小于 \(2^{30}\)，前缀求值的乘加小于 \(2^{60}\)，计算新位的乘法小于 \(2^{62}\)， 都能使用 uint64_t。四次恢复调用显式给出位编号，让编译器看到固定模数； 逆元在编译期求出。第一个前缀位可能大于当前模数，所以减法先加两倍模数， 保证不会在取模前无符号下溢。最后再用同样的从高位向低位计算顺序，把五位 累积进 uint64_t，溢出后正好得到需要的低 64 位。

传入 ACL 的转换后数组采用移动传参。算法仍是五模数 CRT，没有新增长整数 运行时依赖或 SIMD 后端；时间 \(O((n+m)\log(n+m))\)、空间 \(O(n+m)\)，短边分支 时间 \(O(nm)\)。

十进制大指数模幂：短指数快速幂与固定十次方

decimal_power_mod(base,exp,mod) 计算 \(\mathrm{base}^{\mathrm{exp}}\bmod\mathrm{mod}\)。exp 是非空的 十进制数字串，可以带前导零，也可以来自没有零结尾的 string_view 子串。 mod 必须为正，base 与 mod 均支持完整 uint64_t 范围，不要求互质。 \(0^{0}\) 定义为 \(1\bmod\mathrm{mod}\)，所以 \(\mathrm{mod}=1\) 时也返回 0。输入字符串保持不变。

先去掉前导零；全零指数直接返回单位元。底数约减后为 0、1 时直接返回， 为 \(\mathrm{mod}-1\) 时只看指数最后一位的奇偶。不超过 19 位的指数一定能装入 uint64_t，直接解析并使用普通二进制快速幂，避免为了短指数预计算整个表。 20 位及以上保留逐位算法，不把长指数强行转成整数，也不依赖欧拉降幂或分解模数。

对长指数预先保存底数的 0–9 次幂。若已读前缀对应的余数为 \(r\)，接下来读到 数字 \(d\)，新余数为 \(r^{10}\mathrm{base}^d\bmod\mathrm{mod}\)。例如指数从 12 变为 123， 对应 \(\mathrm{base}^{123}=(\mathrm{base}^{12})^{10}\mathrm{base}^3\)。十次方使用 \(x_2=r^2,\quad x_4=x_2^2,\quad x_8=x_4^2,\quad x_{10}=x_8x_2\)，只需四次模乘；再乘表中第 \(d\) 项。 第一位直接从表中取得。若中途余数变成零，后续数字只会继续得到零，可以结束。

所有模乘先转为 unsigned __int128，完整乘积不会丢失高位。Debug 模式会先 检查全部字符，所以快速返回也不会漏掉后面的非法字符。固定 64 位运算模型下， 时间为 \(O(d)\) 次模运算、额外空间 \(O(1)\)，\(d\) 为输入位数；不声明任意精度整数的 位运算复杂度。

任意模行列式：保留欧几里得消元，减少宽整数取模

determinant_mod(mat,mod) 接受方阵和正的 int64_t 模数，矩阵元素可以覆盖 完整有符号 64 位范围。返回值在 \([0,\mathrm{mod})\) 中，不要求模数为素数或主元可逆。 空矩阵的行列式为 \(1\bmod\mathrm{mod}\)，\(\mathrm{mod}=1\) 时返回 0。参数按值接收，传入左值时 保留原矩阵；不再需要输入时可以移动传参以避免复制。

继续使用整数欧几里得消元。设当前主元为 \(a\)、下一行该列为 \(b\)，令 \(q=\left\lfloor\frac ab\right\rfloor\)， 把主元行减去 \(q\) 倍下一行，再交换两行。该列变为 \((b,a\bmod b)\)，最终把下一行 该列消成零；交换行的次数只需记录奇偶。例如模 12 下，矩阵 [[6,5],[4,7]] 依次得到 [[4,7],[2,10]]、[[2,10],[0,11]]， 两次交换抵消，结果为 \(2\cdot11\equiv10\pmod{12}\)。整个过程不需要对 2 或 4 求模逆。

商为 0 时只有行交换，不更新其余元素；商为 1 时直接相减。首列项直接使用 普通整数余数，其余项先求乘积的余数，再用有符号 64 位减法调整到 \([0,\mathrm{mod})\)。 当 \(\mathrm{mod}\le2^{32}\) 时，两因子均小于 mod，乘积能放进 uint64_t；更大模数继续 使用 unsigned __int128。约减后的两个数相减不会超出 int64_t 范围。 输入已在合法剩余范围内时省去重复取模，行交换的负号最后统一处理。

已消元部分与剩余部分构成块上三角矩阵，因此已累乘的对角线乘积变成零后， 最终行列式必为零，可以提前返回；这一点对合数模数同样成立。

复杂度可比逐对估计更紧：一列中完成一对行的消元后，主元从 \(a\) 变成 \(\gcd(a,b)\)。 这次欧几里得步骤数为 \(O\left(1+\log\frac{a}{\gcd(a,b)}\right)\)；处理后续行时，这些对数项 会望远镜相消，所以一列总共 \(O(n+\log \mathrm{mod})\) 次行操作。总时间为 \(O(n^{3}+n^{2}\log(\mathrm{mod}+1))\) 次固定宽度算术操作，空间 \(O(n^{2})\)。

狄利克雷前缀：商值下标、输入含义与运算要求

dirichlet_quotients(n) 按递增顺序返回所有不同的 \(\left\lfloor\frac ni\right\rfloor\)，要求 \(n\ge 1\)。 卷积和求逆接口接收的是函数在这些位置的前缀和，结果也是同一组位置的前缀和。 例如 \(n=10\) 时，商值为 [1,2,3,5,10]；恒一函数的输入也是 [1,2,3,5,10]， 它与自身卷积得到约数个数函数，输出为 [1,3,5,10,27]。 输入中从 3 到 5 的差值 2 表示整个 \((3,5]\) 区间的总和，不能当作 \(f(5)\)。

令 \(s=\lfloor\sqrt n\rfloor\)。当 \(n\ge s(s+1)\) 时，商值由 \(1,\ldots,s\) 和 \(\lfloor n/s\rfloor,\lfloor n/(s-1)\rfloor,\ldots,n\) 两段构成；否则第一段到 \(s-1\)，避免重复 \(s\)。 商值列表直接生成这两段，不再构造一个无用途的值表。运算内部仍保留 0 号哨兵； 返回时移除哨兵并转移结果数组，仍需线性移动元素，但不再分配并复制一份结果。 调用者的输入数组保持不变。

当 \(b\le s\) 时，乘积下标使用等式

\[ \left\lfloor\frac{n}{l\lfloor n/b\rfloor}\right\rfloor =\left\lfloor\frac bl\right\rfloor. \]

因为此时 \(\left\lfloor\frac{n}{\lfloor n/b\rfloor}\right\rfloor=b\)，再除以 \(l\) 就能直接得到反向商值下标。

卷积要求 T 支持交换环运算，不要求比较或除法；求逆额外要求 \(f(1)\) 可逆。 合数模数下“非零”不等于“可逆”，例如模 12 的 5 可用，6 不可用。 卷积和逆运算要求 \(\lvert Q_n\rvert+1\) 可由 int 表示，并为 \(O(\sqrt{n})\) 个值提供内存。

两种运算的保守时间界写作 \(O(n^{2/3} \log(n+1))\) 次算术操作，空间 \(O(\sqrt{n})\)；商值枚举时间和空间均为 \(O(\sqrt{n})\)。 \(\mathrm{arg}^2\le\mathrm{spl}\) 改写为等价的 \(\mathrm{arg}\le\lfloor\sqrt[3]{n}\rfloor\)，避免为判断先形成大平方。

离散对数：最小解与按需建立 BSGS 表

discrete_log(base,target,mod) 和别名 exbsgs 返回满足 \(\mathrm{base}^x\equiv\mathrm{target}\pmod{\mathrm{mod}}\) 的最小非负整数 \(x\)；无解为 nullopt。 三项参数均为 uint64_t，要求 \(\mathrm{mod}\ge 1\)，base 和 target 在内部取模。 \(\mathrm{mod}=1\) 时返回 0；其余情况下 \(\mathrm{target}\equiv 1\) 时也返回 0，包括 \(\mathrm{base}=0\) 的情况。 返回类型是 optional<uint64_t>，答案 0 是有解，不能与无解混淆。

非互质情况沿用逐次约去 gcd 的方法，每次约去前先检查当前指数是否已经满足。 例如 \(4^x\equiv8\pmod{14}\)，\(x\ge 1\) 时约去 \(\mathrm{gcd}=2\)，变为 \(2\cdot4^{x-1}\equiv4\pmod7\)，再乘 2 的逆元，得到 \(4^{x-1}\equiv2\pmod7\)。 最小的 \(x-1\) 是 2，所以结果为 3。接口无须调用者先保证 base 与 mod 互质。

进入互质部分后，幂一定是单位元；若 target 与剩余模数不互质，可以直接判无解。 取 \(B=\lceil\sqrt{\mathrm{mod}}\rceil\)，按指数递增生成 \(1,\mathrm{base},\ldots,\mathrm{base}^{B-1}\)。 途中遇到 target 就返回当前指数；若先回到 1，整个周期已经枚举完，故无解。 哈希表先自然增长，确实走到第 64 步时再预留完整的 BSGS 空间。 64 只决定预分配时机，不限制可求的答案；小指数和短周期无需先分配大表。

完整 baby step 生成后，已有的下一项就是 \(\mathrm{base}^{B}\)，直接求它的逆元。 再按 \(j\) 递增查找 \(\mathrm{target}\,(\mathrm{base}^B)^{-j}=\mathrm{base}^i\)，返回 \(jB+i\)。 各块对应不相交的递增指数区间，表中保留最早的 \(i\)，因此仍返回最小解。

互质部分的乘数均已取模；当 \(\mathrm{mod}\le2^{32}\) 时，乘积能放进 uint64_t， 更大的模数用 unsigned __int128。约 gcd 的阶段可能出现尚未约减的乘数， 继续使用完整的宽整数模乘，不能把这一阶段也按剩余模数简单降为 64 位乘法。 模乘辅助函数放在本模板内部，展开时只携带离散对数所需代码。

一般情况期望时间和空间均为 \(O(\sqrt{\mathrm{mod}})\)；64 位参数并不意味着任意大模数 都能在很小的内存里完成完整 BSGS。

除数求和与商值枚举

summatory_divisor_count(n) 返回 \(1,\ldots,n\) 的约数个数之和， summatory_divisor_sum(n) 返回 \(1,\ldots,n\) 的约数和之和；两者返回无符号 128 位整数， \(n=0\) 时返回 0。前者接受 uint64_t，后者要求 \(n\le10^{18}\)。 两者沿 \(\lfloor\sqrt n\rfloor\) 划分整除双曲线，时间 \(O(\sqrt{n})\)、额外空间 \(O(1)\)。

distinct_quotients(n) 按递增顺序返回所有不同的正商值 \(\left\lfloor\frac nx\right\rfloor\)； \(n=0\) 时返回空数组。时间和空间均为 \(O(\sqrt{n})\)，调用者需为结果提供足够内存。