九月 01, 2024

矩阵的转置原理

​ 矩阵乘法矩阵乘法故名思议是两个矩阵之间的乘法操作,定义为矩阵 $A$ 和矩阵 $B$ 相乘得到矩阵 ...

七月 14, 2024

Link-Cut Tree

Link-Cut Tree(动态树)本文章中的部分代码和思路来自于 Link Cut Tree - OI Wiki。 定义LCT 用来解决动态树的问题,即...

七月 13, 2024

单位根反演

单位根反演单位根的定义此处不再赘述,根据单位根的相关性质,我们可以得到: $$[m \mid i] = \frac 1m \sum_{k...

七月 03, 2024

平衡树

平衡树本文章中的部分代码和思路来自于 Treap - OI Wiki 和 Splay 树 - OI Wiki。 平衡树是二叉查找树的一种,二叉查找树有一个...

六月 30, 2024

全局平衡二叉树

引入我们都知道,树链剖分的时间复杂度如下表: 链修改 链查询 子树修改 子树查询 时间复杂度 $O(\log^2 n)$ $O(\log^2...

六月 16, 2024

带权二分(wqs 二分)解析

引入 现在给出 $n$ 个物品和 $k$ 的限制,要求从 $n$ 个物品中选出恰好 $k$ 个物品满足物品权值之和最大/小。 这是 wqs 二...

五月 23, 2024

THUSC 2024 部分题解

THUSC 2024 简要题解T1 弃光魔使的能量塔题意题目大意,给定 $T,d$,$T$ 组数据,每组数据给出 $n_1,n_2,\dots,n_d,p...

四月 23, 2024

后缀数组 & 后缀自动机

后缀数组(SA)定义给定一个字符串 $S{1 \dots n}$,你需要对这个字符串的 $n$ 个后缀按照字典序排序,排序后的下标数组就是 $sa_i$,...

四月 22, 2024

多项式计数

斯特林数快速计算第二类斯特林数设 $\begin{Bmatrix} n \\ m\end{Bmatrix}$ 表示 $n$ 个数划分成 $m$ 个集合的方...

四月 22, 2024

回文自动机

回文自动机(PAM)回文自动机是一种高效处理回文串相关操作的数据结构,这一节我们专门描述回文自动机以及其扩展应用。 定理:一个字符串中的本质不同回文子串...

加载更多