Skip to content

竞赛规模 Benchmark

以下是固定输入的实测用时。每项单独运行，输入种子为 1；预热 1 次后取 5 次运行的中位数。输入生成不计时，构建、计算、结果消费及临时对象销毁计入时间。

规模按常见竞赛题目的数据范围选取，每项参数列于下表。

持久化仿射线段树、并查集与队列保留全部版本；每 8 次操作从随机历史版本分支 1 次，其余延续最新版本。数据结构测试的数值默认取 \([0,10^9)\)；区间由两个随机端点确定。Beats 的初值取 \([0,10^6)\)，更新参数取 \([-10^6,10^6]\)。

动态树的父亲从编号较小的点中选取，换父亲时保持此约束；二维、三维坐标与查询端点取 \([0,10^9)\)。可排序线段树使用不同的键，替换时分配新键，聚合值为模 998244353 的仿射函数。

区间不同数测试的值域为 \([0,\max(1,\lfloor n/8\rfloor))\)。严格众数测试把序列分为三段，每段以 \(3/4\) 的概率取该段编号，其余取 \([0,8)\) 的值；更新采用相同分布。位集初值与掩码的各位等概率为 0 或 1，移位量取 \([1,1000]\)。

哈希表的输入键固定，哈希函数保留库默认的进程随机盐。矩形仿射更新测试依次为每个点赋值，尚未激活的点不受之前的矩形更新影响。

带偏移哈希表每次合并前，左表偏移取 \([0,10^9)\)，右表偏移取 \((-10^9,0]\)；查询键取 \([0,n)\)。

区间并查集第 \(i\) 步随机选 \(1\le\ell\le i\) 和 \(0\le a\le i-\ell\)，合并 \([a,a+\ell)\) 与 \([i-\ell+1,i+1)\)，\(1\le i<n\)；每步恰好把一个新点加入已连通前缀。

分数测试的第一个分子取 \([-10^9,10^9]\)，两个分母及第二个分子取 \([1,10^9]\)；约分后的结果均可用 64 位有符号整数表示。

一般多点求值和插值使用打乱顺序的 \(1,\ldots,n\)；多项式系数、给定点值及一次因子的根随机取模 998244353。

Stirling 查询的行下标 \(a\) 随机取 \([0,10^{18}]\)；列下标 \(b\) 交替取 \([0,a]\) 中的随机值和 \(a-\min(a,d)\)，其中 \(d\) 随机取 \([0,p)\)。

\(q\)-组合数查询先在 \([0,n]\) 取 \(a\)，再在 \([0,a]\) 取 \(b\)；第一项固定为 \((n,\lfloor n/2\rfloor)\)，确保预处理覆盖整个参数范围。

线性递推的初值与系数随机取模 998244353，最后一个递推系数固定为 1；Berlekamp–Massey 的输入为独立随机序列。

矩阵元素随机取模 998244353；方程组先生成随机解 \(x\)，再以 \(b=Ax\) 构造右端，生成输入不计时。

测试 数据规模 \(n\) 用时（ms） 测试内容
fenwick 200,000 6.957 建立 \(n\) 个位置的树，单点加和区间求和各 \(n\) 次
sparse_table 200,000 14.644 构建 \(n\) 个数的 RMQ，查询 \(n\) 次
segtree 200,000 24.953 构建 \(n\) 个数；交替执行单点赋值与区间求和，各 \(n\) 次
lazy_segtree 200,000 324.044 构建 \(n\) 个数；区间仿射变换与求和各 \(n\) 次，模 998244353
segment_tree_beats 200,000 278.774 构建 \(n\) 个数；区间加、chmin、chmax、求和交替，共 \(n\) 次
sparse_segtree 200,000 103.960 坐标域 \([0,10^9)\)；单点赋值与区间求和各 \(n\) 次
disjoint_sparse_table 200,000 16.026 构建 \(n\) 个数的不相交稀疏表，区间求和 \(n\) 次
wavelet_matrix 200,000 224.503 构建 \(n\) 个数；区间第 \(k\) 小与小于阈值的计数各 \(n\) 次
persistent_order_statistics 200,000 237.258 构建 \(n\) 个前缀版本，区间第 \(k\) 小查询 \(n\) 次
persistent_affine_segtree 50,000 84.269 构建 \(n\) 个数；仿射更新 \(n\) 个版本，新旧版本各求和 \(n\) 次，模 998244353
persistent_dsu 100,000 90.657 \(n\) 个点；合并产生 \(n\) 个版本，新旧版本各查询连通性 \(n\) 次
rollback_dsu 200,000 12.679 \(n\) 个点；合并 \(n\) 次后逐次撤销，每次合并与撤销后查询连通性
potentialized_dsu 200,000 5.605 \(n\) 个点；添加一致的势差约束与查询势差各 \(n\) 次
binary_trie 200,000 199.673 插入 \(n\) 个 30 位数；删除、插入、最小 XOR 查询各 \(n\) 次
fastset 200,000 3.079 值域 \([0,n)\)；切换元素是否存在、前驱查询、后继查询各 \(n\) 次
implicit_lazy_treap 200,000 1031.917 构建长为 \(n\) 的序列；翻转、仿射更新、删除后插入、区间求和交替，共 \(n\) 轮
persistent_queue 200,000 19.337 从空队列产生 \(n\) 个版本；每三次操作两次入队、一次出队，空队列改为入队
double_ended_heap 200,000 35.388 插入 \(n\) 个数；交替弹出最小值或最大值，再插入，共 \(n\) 轮
sliding_window_aggregation 200,000 0.502 扫描 \(n\) 个数，查询所有宽度为 \(\min(n,1000)\) 的窗口最小值
link_cut_tree 100,000 350.254 构建 \(n\) 点树；换父亲、单点赋值、路径求和各 \(n\) 次
sparse_fenwick_2d 100,000 406.420 注册并构建 \(n\) 个二维坐标；单点加与矩形求和各 \(n\) 次
kd_tree 200,000 148.322 构建 \(n\) 个二维点的 KD-tree，最近邻查询 \(n\) 次
sortable_segment_tree 50,000 390.441 构建 \(n\) 个不同键的序列；升序、降序、单点替换交替，共 \(n\) 轮，每轮查询区间函数复合
top_k_sum 200,000 228.697 插入 \(n\) 个数；替换一个数、调整 \(k\) 并查询前 \(k\) 大之和，共 \(n\) 轮，\(k=\lfloor n/2\rfloor\) 与 \(\lfloor n/2\rfloor+1\) 交替
point_set_range_freq 200,000 190.358 构建 \(n\) 个数；单点赋值与区间指定值出现次数查询各 \(n\) 次，值域 \([0,1024)\)
static_range_distinct 200,000 29.009 \(n\) 个数，离线查询 \(n\) 个区间的不同数个数
mo_distinct 100,000 35.484 \(n\) 个数，用莫队回答 \(n\) 个区间的不同数个数，包含查询排序
dynamic_range_majority 200,000 135.096 预处理 \(n\) 个初值与 \(n\) 次待更新值；交替单点赋值与区间严格众数查询，各 \(n\) 次
dynamic_bitset 200,000 13.217 构建两个 \(n\) 位的位集；左移、与固定掩码异或、统计置位数，共 1000 轮
rectangle_sum 200,000 140.707 \(n\) 个带权二维点，离线回答 \(n\) 个矩形求和查询
offline_rectangle_add_rectangle_sum 100,000 117.342 \(n\) 个带权矩形，离线回答 \(n\) 个矩形覆盖权值总和查询，模 998244353
mo_with_updates_distinct 100,000 851.927 \(n\) 个数，交替单点赋值与区间不同数查询各 \(n\) 次；带修改莫队，包含预处理与排序
static_range_inversions 100,000 627.122 构建 \(n\) 个数的静态区间逆序对结构，查询 \(n\) 次
leftist_heap 200,000 63.569 建立 \(n\) 个单元素左偏堆，逐层两两合并共 \(n-1\) 次，再依次弹出 \(n\) 个最小值
cdq_dominance 200,000 195.905 \(n\) 个三维点，统计各坐标均不大于当前点的点数，包含自身与重复点
hashmap 200,000 62.524 预留容量并插入 \(n\) 个 64 位键；赋值、已有键查询、独立键查询、删除、重新插入各 \(n\) 次
range_linear_add_range_min 100,000 684.930 构建 \(n\) 个数；区间加 \(ai+b\) 与独立区间最小值查询各 \(n\) 次，\(\lvert a\rvert\le1000,\lvert b\rvert\le10^6\)
rectangle_affine_kd_tree 50,000 1636.557 预处理 \(n\) 个二维点，初始激活前一半；点赋值、矩形仿射更新与独立矩形求和各 \(n\) 次，模 998244353
static_range_mode 100,000 194.480 构建 \(n\) 个数；查询 \(n\) 个区间的众数及出现次数，值域 \([0,\max(1,\lfloor n/8\rfloor))\)
sparse_range_affine_sum 50,000 121.712 初值为零，坐标域 \([0,10^9)\)；区间仿射更新与独立区间求和各 \(n\) 次，模 998244353
range_set_range_product 200,000 234.351 构建 \(n\) 个仿射函数；区间赋值与独立区间函数复合各 \(n\) 次，模 998244353
static_range_xor_basis 100,000 23.409 构建 \(n\) 个 30 位数；区间最大 XOR 与可表示性查询各 \(n\) 次，短区间与任意区间交替，短区间长度不超过 30
static_range_lis_query 100,000 235.742 预处理长为 \(n\) 的随机排列，查询 \(n\) 个区间的严格 LIS 长度
mergeable_frequency_tree 100,000 203.915 建立 \(n\) 棵单元素频次树并逐层合并；区间计数、分裂、第 \(k\) 小查询及合并回原树，共 \(n\) 轮，值域 \([0,n)\)，空树跳过第 \(k\) 小查询
fractional_cascading 200,000 253.710 从总长 \(n\) 的 \(\min(n,32)\) 个有序数组构建；查询 \(n\) 次在所有数组中的 lower_bound，输入排序不计时
rollback_mo_weighted_frequency 100,000 204.942 \(n\) 个数、\(n\) 个区间；回滚莫队求每个区间内 \(\max_v v\cdot\mathrm{freq}(v)\)，值域 \([1,\max(1,\lfloor n/8\rfloor)]\)，包含查询排序
range_parallel_dsu 200,000 63.746 \(n\) 个带权点；逐点扩展连通前缀，执行 \(n-1\) 次等长区间对应合并，每次返回同分量无序点对的权值乘积和，模 998244353，包含初始化
fenwick_2d 1,000 36.014 构建 \(n\times n\) 的全零网格；随机单点加与独立矩形求和各 \(200n\) 次
implicit_treap 200,000 1026.339 构建 \(n\) 个仿射函数的序列；翻转、单点赋值、删除后插入交替，共 \(n\) 轮，每轮查询区间函数复合，模 998244353
potentialized_group_dsu 200,000 15.841 \(n\) 个点，势为模 998244353 的行列式为 1 的 \(2\times2\) 矩阵；添加一致的相对变换约束与独立势差查询各 \(n\) 次
common_interval_decomposition_tree 200,000 11.782 构建长为 \(n\) 的随机排列的公共区间分解树，包含遍历结果节点
offline_rectangle_add_point_get 200,000 177.570 \(n\) 个带权矩形，离线回答 \(n\) 个点的覆盖权值之和
prefix_sum 200,000 2.467 构建 \(n\) 个数的前缀和，区间求和 \(n\) 次
block_range_sum 200,000 48.613 建立 \(n\) 个零的分块数组；单点加与独立区间求和各 \(n\) 次
range_add_point_get 200,000 12.987 建立 \(n\) 个零的差分树状数组；区间加与独立单点查询各 \(n\) 次
cartesian_tree 200,000 2.103 构建 \(n\) 个数的最小笛卡尔树，包含遍历根、父亲与左右孩子
consecutive_segment 200,000 151.565 从 \(n\) 个数逐点建立连续段结构；区间赋值与独立单点查询各 \(n\) 次，赋值左端点均匀取 \([0,n)\)，长度均匀取 \([1,\min(100,n-l)]\)；包含消费被覆盖段
tag_hashmap 200,000 230.161 建立 \(n\) 个单元素哈希表，键取 \([0,\max(1,\lfloor n/8\rfloor))\)；逐层两两合并前各加整体偏移，重复键取最小值，合并后释放来源表；最后查询 \(n\) 次并遍历结果
dijkstra 200,000 65.346 \(n\) 个顶点、\(4n\) 条有向边，单源最短路
convex_polygon 200,000 41.470 按边界顺序给出 \(n\) 个点 \((x,x^2)\)，\(x=i-\lfloor n/2\rfloor,0\le i<n\)；构建后作 \(n\) 次点定位，查询横坐标取同一范围的整数，纵坐标取 \([0,\lfloor n^2/4\rfloor]\) 中整数，行列式使用有符号 128 位整数
circle_overlap_area 200,000 92.145 计算 \(n\) 对圆盘的相交面积，圆心各坐标和半径独立取整数 \([0,10^6]\)，运算使用 long double
circle_polygon_area 200,000 35.741 圆心在原点、半径 1000 的圆盘与 \(n\) 边形求交面积；顶点极角等间隔、半径独立取整数 \([800,1200]\)，运算使用 long double
convex_hull 200,000 23.168 \(n\) 个随机整数点，各坐标取 \([-10^9,10^9]\)；计算严格凸包，包含排序和结果遍历，坐标运算使用有符号 128 位整数
convex_hull_boundary 200,000 19.575 打乱顺序的 \(n\) 个点 \((x,x^2)\)，\(x=i-\lfloor n/2\rfloor,0\le i<n\)，全部位于凸包边界；包含排序和结果遍历，坐标运算使用有符号 128 位整数
minkowski_sum 200,000 46.052 两个各有 \(n\) 个随机整数点的集合，各坐标取 \([-10^9,10^9]\)；求凸包 Minkowski 和，包含凸包预处理和结果遍历，坐标运算使用有符号 128 位整数
minkowski_sum_boundary 200,000 41.901 两个各有 \(n\) 个点 \((x,x^2)\) 的集合，\(x=i-\lfloor n/2\rfloor,0\le i<n\)，分别打乱顺序；求 Minkowski 和，包含凸包预处理和结果遍历，坐标运算使用有符号 128 位整数
closest_pair 200,000 40.564 \(n\) 个随机整数点，坐标取 \([-10^9,10^9]\)；求最近点对，包含排序与分治
furthest_pair 200,000 19.474 \(n\) 个随机整数点，坐标取 \([-10^9,10^9]\)；求最远点对，包含排序、凸包与旋转卡壳
rectangle_union_area 200,000 391.882 \(n\) 个半开轴对齐矩形；横纵端点独立取整数 \([0,10^9]\) 后排序；计算并面积，包含坐标压缩、事件排序与扫描线
triangle_point_counter 600 58.835 \(n\) 个查询顶点和 \(n\) 个待统计点，各坐标独立取整数 \([0,10^6]\)；预处理后随机查询 \(n^2\) 个三角形的严格内部点数
triangle_counter_grid 600 53.823 \(n\) 个查询顶点和 \(n\) 个待统计点，各坐标独立取整数 \([0,31]\)，允许重复；预处理后随机查询 \(n^2\) 个三角形的严格内部点数
euclidean_mst 200,000 281.251 \(n\) 个随机整数点，坐标取 \([-10^9,10^9]\)；通过 Delaunay 候选边求欧氏最小生成树，包含点排序、三角剖分和 Kruskal
circumcircle 200,000 4.062 \(n\) 组三点外接圆查询；每组取随机平移 \([-10^9,10^9]^2\)，三个点的各坐标偏移取整数 \([-1000,1000]\)，共线时返回空结果
minimum_enclosing_circle 200,000 28.171 \(n\) 个随机整数点，坐标取 \([-10^9,10^9]\)；计算最小覆盖圆，包含随机打乱与整数包含判定
minimum_circle_boundary 200,000 29.188 \(n\) 个随机整数点，坐标取 \([-10^9,10^9]\)；构造最小覆盖圆并精确标记圆周上的输入点，包含随机打乱与边界扫描
convex_layers 100,000 345.528 \(n\) 个互异随机整点，坐标取 \([-10^9,10^9]\)；计算每个点所属的凸包层，包含排序与逐层删除边界
convex_layers_grid 100,000 76.426 按行取宽为 \(\max(1,\lfloor\sqrt n\rfloor)\) 的网格前 \(n\) 个整点，乱序输入；计算每个点所属的凸包层，包含排序与逐层删除边界
half_plane_intersection 100,000 48.955 半径 1000 的圆周分成 \(n\) 个等角区间，每段中间 80% 随机取一点，连接相邻点形成半平面；乱序输入，全部边界有效，包含排序与交集面积计算
half_plane_redundant 100,000 44.828 \(n\) 个包含原点的随机半平面，方向均匀，边界到原点的距离取整数 \([1,1000]\)；另加 \([-2000,2000]^2\) 边界，包含排序与交集面积计算
parallel_binary_search 200,000 154.689 \(n\) 个点按随机顺序加入一棵随机树的 \(n-1\) 条边；用并查集与整体二分求 \(n\) 对点首次连通的边前缀长度，包含每轮重建并查集
larsch 200,000 23.209 在线计算 \(n\) 个 DP 状态，\(d_0=0\)，\(d_i=\min_{0\le j<i}\{d_j+(s_i-s_j)^2+10^5\}\)；\(s_0=0\)，前缀增量独立取 \([1,10]\)，输入生成不计时
smawk 200,000 9.742 求隐式 \(n\times n\) Monge 矩阵 \(a_{ij}=(x_i-y_j)^2+b_j\) 的所有行最小值位置；两个非降坐标序列的增量独立取 \([0,10]\)，列偏置取 \([-5\cdot10^5,5\cdot10^5]\)，输入生成不计时
monotone_cht 200,000 2.186 单调 CHT 交替加入直线与查询最小值，各 \(n\) 次；第 \(i\) 次斜率 \(n-i\)、横坐标 \(n-2i\)，\(0\le i<n\)，截距随机取 \([-10^6,10^6]\)
dynamic_cht 200,000 10.854 动态直线容器交替加入直线与查询最小值，各 \(n\) 次；斜率、截距与查询横坐标独立随机取 \([-10^6,10^6]\)
cht_xy 200,000 29.984 动态加入 \(n\) 个二维点，每次加入后查询一个独立方向的最小、最大点积；点与方向的各分量随机取 \([-10^6,10^6]\)，整数交点精确比较
simplex 200 56.779 求解 \(n\) 个变量、\(2n\) 条约束的稠密线性规划；\(n\) 条随机约束系数取 \([0,100]\)，右端取 \(n\cdot[25,50]\)，另有 \(0\le x_j\le10\)，目标系数取 \([1,100]\)；包含表构建与最优解遍历
simplex_phase_one 200 200.729 求解 \(n\) 个变量、\(3n\) 条约束的稠密线性规划；随机约束系数取 \([0,100]\)，右端取 \(\max(n\cdot[75,100],\sum_j a_{ij})\)，另有 \(1\le x_j\le10\)，目标系数取 \([1,100]\)；包含第一阶段可行解搜索、表构建与最优解遍历
adaptive_simpson 1,000 7.581 在 \(n\) 个随机区间上积分 \(e^{-x^2}\)；端点取 \([-5,5]\) 中间隔为 \(10^{-3}\) 的网格，使用 double，误差估计目标 \(10^{-10}\)，递归深度上限 24
hex_division 100,000 12.317 \(n\) 位随机十六进制整数除以 \(\max(1,\lfloor n/2\rfloor)\) 位随机非零整数；包含解析、除法与商余数输出
hex_division_short 100,000 1.161 \(n\) 位随机十六进制整数除以 8 位随机非零整数；包含解析、除法与商余数输出
multiplicative_function_sum 100,000,000,000 753.096 计算 \(\sum_{i=1}^n f(i)\)，其中 \(f\) 为积性函数、\(f(p^e)=7e+11p\)；系数模 469762049，包含筛素数、商分块表与递归求和
set_egf_composition 131,072 97.886 在 \(\log_2 n\) 个变量上计算集合幂级数的 EGF 复合；输入含 \(n\) 个随机系数，常数项为零，外层含 \(\log_2 n+1\) 个随机 EGF 系数；模 998244353，包含变换与结果遍历
set_polynomial_composition 131,072 97.810 将含 \(n\) 个随机系数的集合幂级数代入一个含 200 个随机系数的普通多项式；模 998244353，包含导数计算、变换与结果遍历
set_power_projection 131,072 70.329 含 \(n\) 个随机系数的集合幂级数与 \(n\) 个随机权值，计算第 0 至 999 次幂的加权系数和；模 998244353，包含转置复合、幂投影与结果遍历
prime_multiplicative 200,000 32.869 两个长为 \(p\) 的随机序列作下标模素数 \(p\) 的乘法卷积，\(p\) 是不小于 \(\max(2,n)\) 的最小素数；系数模 998244353，包含原根搜索、变换与结果遍历
power_of_two_multiplicative 262,144 14.867 两个长为 \(n\) 的随机序列作下标模 \(n\) 的乘法卷积，\(n\) 为 2 的幂；系数模 998244353，包含分层、变换与结果遍历
multivariate_truncated 131,072 45.572 两个各有 \(n\) 个随机系数的多项式相乘；最多三个变量，各维截断长度为 2 的幂，指数之差不超过 1，乘积为 \(n\)；模 998244353，包含混合进制编码、变换与结果遍历
multivariate_truncated_binary 131,072 302.746 两个各有 \(n\) 个随机系数的多项式相乘，\(\log_2 n\) 个变量各截断至次数小于 2，模 998244353；包含混合进制编码、变换与结果遍历
multivariate_cyclic 131,072 219.265 两个各有 \(n\) 个随机系数的多项式作多元循环卷积；最多三个变量，各维长度为 2 的幂，指数之差不超过 1，乘积为 \(n\)，模 998244353；包含原根与变换预处理、变换和结果遍历
multivariate_cyclic_crt 256 395.109 两个各有 \(479n\) 个随机系数的多项式作 \(479\times n\) 的二维循环卷积，模 1004535809；包含原根与变换预处理、CRT 卷积和结果遍历
multivariate_cyclic_u64 4,096 75.073 两个各有 \(n\) 个随机系数的多项式作循环卷积，模 \(p=2^{64}-2^{32}+1\)；包含原根与变换预处理、系数分块和结果遍历
li_chao_lines 200,000 89.950 构建 \(n\) 个离散坐标的 Li Chao 树；交替加入直线与单点求最小值，各 \(n\) 次；坐标从 \(-5n\) 随机递增 \(1\) 至 \(10\) 后打乱，斜率与截距取 \([-10^6,10^6]\)，包含排序建树
li_chao_segments 100,000 84.857 构建 \(n\) 个离散坐标的 Li Chao 树；交替加入随机非空半开区间上的线段与独立单点求最小值，各 \(n\) 次；坐标从 \(-5n\) 随机递增 \(1\) 至 \(10\) 后打乱，斜率与截距取 \([-10^6,10^6]\)，包含排序建树，查询允许未覆盖坐标
concave_concave_maxplus 200,000 2.094 两个长为 \(n\) 的凹序列求 max-plus 卷积；初值取 \([-5\cdot10^5,5\cdot10^5]\)，斜率从 \(n\) 开始，每步随机减少 \(0\) 至 \(4\)，包含结果遍历
arbitrary_concave_maxplus 200,000 13.242 两个长为 \(n\) 的序列求 max-plus 卷积；一个任意，另一个凹，初值及任意项取 \([-5\cdot10^5,5\cdot10^5]\)，凹序列斜率从 \(n\) 开始，每步随机减少 \(0\) 至 \(4\)，包含结果遍历
convex_convex_minplus 200,000 2.039 两个长为 \(n\) 的凸序列求 min-plus 卷积；初值取 \([-5\cdot10^5,5\cdot10^5]\)，斜率从 \(-n\) 开始，每步随机增加 \(0\) 至 \(4\)，包含结果遍历
arbitrary_convex_minplus 200,000 13.182 两个长为 \(n\) 的序列求 min-plus 卷积；一个任意，另一个凸，初值及任意项取 \([-5\cdot10^5,5\cdot10^5]\)，凸序列斜率从 \(-n\) 开始，每步随机增加 \(0\) 至 \(4\)，包含结果遍历
concave_arbitrary_minplus 100,000 25.026 两个长为 \(n\) 的序列求 min-plus 卷积；一个凹，另一个任意，初值及任意项取 \([-5\cdot10^5,5\cdot10^5]\)，凹序列斜率从 \(n\) 开始，每步随机减少 \(0\) 至 \(4\)，包含结果遍历
suffix_automaton 1,000,000 134.394 构建 \(n\) 个小写字母的后缀自动机
xor_convolution 1,048,576 20.308 两组长度 \(n\) 的数组，模 998244353 的 XOR 卷积
factorize 1,000 27.059 分解 \(n\) 个无符号 64 位整数
prime_table 1,000,000 6.348 筛出不超过 \(n\) 的最小质因子、\(\varphi\) 与 \(\mu\)
segmented_sieve 100,000,000 120.118 分段枚举不超过 \(n\) 的所有素数；每段至多 \(2^{20}\) 个奇数，包含基础素数筛、回调及结果消费
squarefree_count 1,000,000,000,000 1.241 计算不超过 \(n\) 的无平方因子正整数个数，包含 Möbius 表与 Mertens 前缀表构建
prime_summatory 100,000,000,000 322.332 用商值筛同时计算 \(\pi(n)\) 和不超过 \(n\) 的素数和，包含商值表构建
divisor_table 1,000,000 13.716 筛出不超过 \(n\) 的约数个数与约数和
dujiao_sieve 1,000,000 15.936 构建不超过 \(n\) 的 \(\varphi\) 与 \(\mu\) 前缀表
divisor_count 1,000,000,000,000 2.193 求 1 至 \(n\) 的约数个数之和
divisor_sum 1,000,000,000,000 2.300 求 1 至 \(n\) 的约数和之和
distinct_quotients 1,000,000,000,000 11.619 枚举所有不同的 \(\lfloor n/x\rfloor\)
subset_sum 10,000 9.730 \(n\) 个 \([1, 1000]\) 权值，容量为总和的一半
subset_sum_counts 200,000 330.842 \(n\) 个 \([1,n]\) 正整数，统计目标和 \(0\) 到 \(n\) 的子集个数，模 998244353，包含频次统计与形式幂级数 exp
knapsack 200,000 4.748 \(n\) 个物品，重量 \([1, 50]\)、价值小于 \(10^9\)，容量 1000
subarray_gcd 200,000 109.875 \(n\) 个 \([0, 10^6]\) 整数，统计各子数组 gcd
range_gcd_changes 200,000 29.055 \(n\) 个 \([0,10^6]\) 整数；列出每个左端点的区间 gcd 变化及其首次出现的右端点，包含结果遍历
montmort 1,000,000 7.580 生成到 \(n\) 的错排数，模 \(2^{64}-1\)
tetration_mod 10,000 56.639 \(n\) 次幂塔；底数、高度小于 \(10^9\)，正模数不超过 \(10^9\)
exponential_polynomial_sum 100,000 5.392 次数为 \(n\)，求 \(\sum_{i=0}^{10^{18}-1}2^i i^n\)，模 998244353
f2_rank 1,024 4.200 复制 \(n\times n\) 二进制矩阵并求秩，每个元素等概率取 0 或 1
polynomial_factorization 200 497.531 分解次数为 \(n\) 的随机首一多项式，模 998244353
fixed_discrete_log 200,000 481.208 预处理模 998244353、原根 3 的表，查询 \(n\) 次离散对数
floor_monoid_product 10,000 19.240 \(n\) 次格点路径矩阵积；路径长度、\(a,b<10^9\)，\(1\le m\le10^9\)，矩阵模 998244353
fraction_arithmetic 200,000 150.594 构造 \(n\) 对分数，每对分别求和、差、积、商
gaussian_gcd 100,000 45.812 求 \(n\) 对高斯整数的 gcd；实部与虚部均取 \([-10^9,10^9]\)
hafnian 32 177.017 求 \(n\times n\) 随机对称矩阵的 hafnian，模 998244353
lagrange_consecutive 200,000 4.496 给定 \(f(0),\ldots,f(n-1)\)，求 \(f(10^{18})\)，模 998244353
power_sum 100,000 3.060 以 \(n\) 为指数，求 \(\sum_{i=1}^{10^{18}}i^n\)，包含点值构建与插值，模 998244353
increasing_sequence_bounds 100,000 555.972 统计长为 \(n\) 的不下降序列；第 \(i\) 项范围 \([\max(0,i-a_i),i+1+b_i)\)，\(a_i,b_i\) 随机取 \([0,n)\)，\(0\le i<n\)，模 998244353
mod_sqrt 10,000 4.911 \(n\) 次模平方根；模数 \(p\) 交替取 \(998244353\) 与 \(10^9+7\)，被开方数随机取 \([0,p)\)
mod_kth_root 1,000 0.964 \(n\) 次模 \(k\) 次根；模数 \(p\) 交替取 \(998244353\) 与 \(10^9+7\)，被开方数随机取 \([0,p)\)，\(k\) 随机取 \([1,p)\)
mod_kth_root_count 10,000 2.238 \(n\) 次模 \(k\) 次根计数；模数 \(p\) 交替取 \(998244353\) 与 \(10^9+7\)，被开方数随机取 \([0,p)\)，\(k\) 随机取 \([1,p)\)
primitive_roots 200,003 16.168 枚举不大于 \(n\) 的最大质数 \(p\) 的所有原根并排序，包含分解 \(p-1\) 与寻找一个原根
stirling_first_small_prime 2,000 24.100 模数 \(p\) 为不大于 \(n\) 的最大质数；构建有符号第一类 Stirling 表并查询 \(50n\) 次，下标不超过 \(10^{18}\)
stirling_second_small_prime 2,000 25.656 模数 \(p\) 为不大于 \(n\) 的最大质数；构建第二类 Stirling 表并查询 \(50n\) 次，下标不超过 \(10^{18}\)
large_factorials 1,000 236.938 计算 \(n\) 个随机参数的阶乘，参数取 \([0,998244353)\)；模 998244353，包含分块预处理与逐个查询的尾段乘积
many_factorials 100,000 1194.338 计算 \(n\) 个随机参数的阶乘，参数取 \([0,998244353)\)；模 998244353，包含分块预处理与批量多点求值
q_binomial_primitive 200,000 6.098 构建并查询 \(n\) 次 \(q\)-组合数，参数 \(0\le b\le a\le n\)，模数 \(p=998244353\)，\(q=3\)
q_binomial_small_order 200,000 2.651 构建并查询 \(n\) 次 \(q\)-组合数，参数 \(0\le b\le a\le n\)，模数 \(p=998244353\)，\(q=3^{(p-1)/1024}\bmod p\) 的阶为 1024
q_binomial_one 200,000 3.523 构建并查询 \(n\) 次 \(q\)-组合数，参数 \(0\le b\le a\le n\)，模数 \(p=998244353\)，\(q=1\)
berlekamp_massey 4,000 14.199 从 \(n\) 项随机序列恢复最短线性递推，模 998244353
linear_recurrence_nth 512 68.094 给定 \(n\) 阶递推，基础算法求第 \(10^{18}\) 项，模 998244353
linear_recurrence_nth_fast 16,384 272.655 给定 \(n\) 阶递推，Bostan–Mori 求第 \(10^{18}\) 项，模 998244353
linear_recurrence_terms 16,384 306.450 给定 \(n\) 阶递推，求从第 \(10^{18}\) 项开始的连续 \(n\) 项，模 998244353
min_of_mod_linear 100,000 23.521 \(n\) 次模一次函数最小值查询；区间长度、模数随机取 \([1,10^9]\)，乘数与常数随机取 \([0,m)\)
minmax_subset_int 1,048,576 7.201 由 \(d=\log_2 n\) 个整数的子集最小值表与最大值表，分别恢复第 \(\lceil d/2\rceil\) 大与小；64 位整数运算，原值取 \([-1000,1000]\)，每张表长 \(n\)，构造表不计时
minmax_subset_mod 1,048,576 7.275 由 \(d=\log_2 n\) 个整数的子集最小值表与最大值表，分别恢复第 \(\lceil d/2\rceil\) 大与小；原值取 \([-1000,1000]\)，表值与运算模 998244353，每张表长 \(n\)，构造表不计时
matrix_rank 512 71.682 求 \(n\times n\) 随机矩阵的秩，模 998244353
pfaffian 512 101.282 求 \(n\times n\) 随机交错矩阵的 Pfaffian，模 998244353；上三角独立随机、对角为零、下三角为上三角的相反数
matrix_determinant 512 71.643 求 \(n\times n\) 随机矩阵的行列式，模 998244353
matrix_inverse 512 422.329 对 \(n\times n\) 随机矩阵求逆，模 998244353
matrix_multiply_mod 512 120.059 两个 \(n\times n\) 随机矩阵相乘，包含转置工作区，模 998244353
matrix_power 64 34.395 用通用矩阵乘法求 \(n\times n\) 随机矩阵的 \(10^{18}\) 次幂，模 998244353
matrix_power_mod 128 148.797 用模整数矩阵乘法求 \(n\times n\) 随机矩阵的 \(10^{18}\) 次幂，模 998244353
linear_system 512 106.939 解有 \(n\) 个方程、\(n\) 个未知数的相容随机线性方程组，返回一个解与零空间基，模 998244353
linear_system_underdetermined 512 40.195 解有 \(\max(1,\lfloor n/2\rfloor)\) 个方程、\(n\) 个未知数的相容随机线性方程组，返回一个解与零空间基，模 998244353
polynomial_division 131,072 58.941 \(n\) 项多项式除以 \(\lceil n/2\rceil\) 项多项式，返回商和余数，模 998244353
polynomial_taylor_shift 131,072 16.677 平移 \(n\) 项多项式，求 \(f(x+71829)\)，模 998244353
multipoint_evaluation 65,536 355.389 \(n\) 项多项式在 \(n\) 个点求值，包含乘积树构建，模 998244353
polynomial_interpolation 65,536 419.446 \(n\) 个不同点的点值插值，包含乘积树构建，模 998244353
monomial_to_newton 100,000 304.140 把 \(n\) 项多项式转换为给定 \(n\) 个节点上的 Newton 基系数，包含乘积树构建；系数与节点独立随机取模 998244353，节点允许重复
nim_product 200,000 4.955 \(n\) 对独立随机的 64 位无符号整数，分别求 nim 乘积；查表初始化在预热中完成
xor_space_intersection 10,000 47.166 \(n\) 组查询，每组两份各含 20 个独立 30 位向量的基；求线性空间交并约化返回的基
rational_approximation 100,000 17.632 \(n\) 次有理数逼近；分子、分母及逼近界限独立取 \([1,10^9]\)
stern_brocot_queries 100,000 13.575 \(n\) 组正分数，每组分别查询指定深度祖先、两点 LCA 和第一点的子树边界；分子分母先独立取 \([1,10^9]\) 再约分，深度取 \([0,99]\)
rational_reconstruction 200,000 13.989 \(n\) 次有理数重构，模数 \(m=998244353\)，剩余值取 \([0,m)\)，分子绝对值与分母上界均为 \(10^4\)；包含无解查询
geometric_evaluation 65,536 15.402 \(n\) 项多项式在 \(7\cdot3^i\) 求值，\(0\le i<n\)，模 998244353
geometric_interpolation 65,536 26.419 从 \(7\cdot3^i\) 的 \(n\) 个点值恢复多项式，模 998244353
polynomial_shift_samples 65,536 17.648 已知 \(f(0),\ldots,f(n-1)\)，求 \(f(71829),\ldots,f(71829+n-1)\)，模 998244353
polynomial_product_sequence 65,536 68.990 计算 \(n\) 个一次因子 \(x-a_i\) 的乘积，模 998244353
polynomial_gcd 32,768 331.795 求次数分别为 \(n\) 和 \(n-1\) 的两个多项式的首一 gcd，模 998244353
polynomial_mod_inverse 32,768 334.316 求 \(n-1\) 次多项式模 \(n\) 次多项式的逆，模 998244353
polynomial_roots 512 57.905 求 \(\prod_{i=0}^{n-1}(x-i)\) 的全部根，模 998244353；构造输入不计时
fps_inverse 131,072 52.898 求 \(1/f\) 的前 \(n\) 项，\(f(0)=3\)，模 998244353
fps_logarithm 131,072 67.957 求 \(\log f\) 的前 \(n\) 项，\(f(0)=1\)，模 998244353
fps_exponential 131,072 155.717 求 \(\exp f\) 的前 \(n\) 项，\(f(0)=0\)，模 998244353
fps_power 131,072 226.297 求 \(f^{10^{18}}\) 的前 \(n\) 项，\(f(0)=3\)，模 998244353
sparse_fps_inverse 200,000 13.715 求稀疏 \(f\) 的逆的前 \(n\) 项；\(f(0)=4\)，随机选取 \(\min(64,n-1)\) 个非零非常数项，模 998244353
sparse_fps_logarithm 200,000 13.454 求稀疏 \(f\) 的对数的前 \(n\) 项；\(f(0)=1\)，随机选取 \(\min(64,n-1)\) 个非零非常数项，模 998244353
sparse_fps_exponential 200,000 12.836 求稀疏 \(f\) 的指数的前 \(n\) 项；\(f(0)=0\)，随机选取 \(\min(64,n-1)\) 个非零项，模 998244353
sparse_fps_power 200,000 27.429 求稀疏 \(f^{10^{18}}\) 的前 \(n\) 项；\(f(0)=4\)，随机选取 \(\min(64,n-1)\) 个非零非常数项，模 998244353
sparse_fps_square_root 200,000 27.488 求稀疏 \(f\) 的平方根的前 \(n\) 项；\(f(0)=4\)，随机选取 \(\min(64,n-1)\) 个非零非常数项，模 998244353
sparse_matrix_determinant 2,000 81.736 求 \(n\) 阶矩阵行列式，包含 \(n\) 条非零对角记录和 \(2n\) 条随机记录，重复位置累加；模 998244353，使用固定投影种子，包含投影与必要的回退
fps_composition 65,536 923.840 两个 \(n\) 项多项式，求 \(f(g(x))\) 的前 \(n\) 项，\(g(0)=17\)，模 998244353
fps_compositional_inverse 65,536 953.651 求 \(f\) 的复合逆的前 \(n\) 项，\(f(0)=0,f'(0)=3\)，模 998244353

下载本次数据

运行环境

  • 时间：2026-10-25 23:23 UTC
  • 提交：d98b67744ba08813fa69ebf1f45234aa78e67b8b
  • 系统：Ubuntu 24.04.5 LTS x86_64
  • CPU：AMD EPYC 7763 64-Core Processor；2 个逻辑核，测试串行运行
  • 编译器：g++-14 (Ubuntu 14.2.0-4ubuntu2~24.04.1) 14.2.0
  • 编译选项：-std=c++23 -O2 -DNDEBUG

复现

bash init.sh
python3 tools/benchmark.py --compiler g++-14

单项测试可使用 build/benchmarks/benchmark <workload> <n> 5。