TH911 Blog

「光阴不可测,岁月亦无歌。」

题解:[春季测试 2023] 圣诞树

洛谷P9119

题目传送门 题意分析 首先确定起点 $k$ 是简单的。记 $a_1,a_2,\cdots,a_n$ 为原来的 $n$ 个点。 可以统一将 $a_1,a_2,\cdots,a_k$ 与 $a_{k+1},a_{k+2},\cdots,a_n$ 交换在序列中的位置,这样便于处理。交换后仍然为凸多边形。 考虑原问题等价于对新的 $a_1,a_2,\cdots,a_{n-1}$ 进行...

各类模板

矩阵乘法 Barrett 约减

矩阵乘法 Matrix,支持二维 initializer_list 初始化。支持矩阵加法、矩阵乘法。重载 +、+=、*、*=。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47...

Barrett 约减

优化整数除法/取模

推荐一篇文章。 Barrett 约减优化整数除法/取模 取变量的模其实是非常慢的,而 Barrett 可以在一定情况下将取模化为两次乘法、一次右移以及至多两次减法。 令模数为 $p$。 容易发现: \[x\bmod p=x-p\left\lfloor\dfrac xp\right\rfloor\] 考虑快速求出 $\left\lfloor\dfrac xp\right\r...

线段树历史操作

历史和线段树

历史和线段树 例题:Loj P193 线段树历史和 您需要写一种数据结构,来维护一个有序数列,其中需要提供以下操作: 区间加一个数。 查询区间的历史和。 历史和定义为数列 $h_i$ 的区间和:初始 $h_i=a_i$,在每次操作(修改或查询)完成后,对所有 $h_i \leftarrow h_i+a_i$。 考虑使用线段树维护区间信息。...

题解:Koishi Loves Number Theory

洛谷P3598

题目传送门 数学推导 首先不难得到: \[\begin{aligned} f(n)&=\sum_{i=0}^nx^i\\ &=\dfrac{x^{n+1}-1}{x-1} \end{aligned}\] 因为 $\operatorname{lcm}\left(\dfrac ac,\dfrac bc\right)=\dfrac{\operatorname{lcm...

题解:最小公倍佩尔数

洛谷P10663

题目传送门 gcd-lcm 容斥 所谓 gcd-lcm 容斥,即对于集合 $T$,有: \[\operatorname*{lcm}_{i\in T}i=\prod_{S\subseteq T}\left(\gcd_{i\in S}i\right)^{(-1)^{\vert S\vert-1}}\] 证明 不妨考虑 $i$ 的质因子。发现对于...

树链剖分详解(长链剖分)

长链剖分应用 | 例题:洛谷P5903 CF1009F

参考资料 例题:P5903 树上 $k$ 级祖先。 例题:CF1009F Dominant Indices。 因为当时写树链剖分详解(重链剖分)时并不会长链剖分,所以只能另开一文了。 「长链剖分」,除「重链剖分」外的另一种树剖方式,与深度相关。 长链剖分 定义「重子节点」表示子树深度最大的子节点,「轻子节点」表示剩余子节点。其余定义同「重链剖分」的...

可持久化并查集

例题:洛谷P3402

例题链接 建议优先阅读可持久化线段树。 可持久化并查集 可持久化并查集,即可撤销并查集,支持回退到之前某个版本信息。 显然需要维护 $f_x$ 为 $x$ 的父节点。使用可持久化线段树维护 $f_x$ 即可。 但是,注意可持久化并查集不能使用路径压缩,只能使用启发式合并优化。否则会破坏历史版本信息。 单次寻找根节点的复杂度为 $\mathcal O(\log n)$。...

函数指针用法

有些时候需要函数指针,例如线段树建树时的初始值。 使用方法: 1 2 3 typedef int (*fp)(int); //... fp func 这样,func(x) 即一个返回 int 的函数。

可持久化 FHQ Treap

例题:洛谷P3835

例题链接 建议优先阅读可持久化线段树。 可持久化 FHQ Treap 同可持久化线段树,可持久化平衡树的原理也是充分利用过去版本信息。 在 split 操作中,不断复制节点即可构造新版本。 是的,结束了。 事实上,诸多可持久化数据结构都是如此原理。 例题 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2...