一、什么是左偏树 1.左偏树简介     左偏树是一棵二叉树。左偏树顾名思义就是往左偏的树，这样方便合并。为什么方便合并呢？我们把要合并的另一棵树与左偏树比较小的右侧合并，就能尽可能让二叉树+堆保...

一、线性求逆元 1. $1\sim n$ 的逆元 单独一个数 $\bmod p$ 的逆元是可以用费马小定理($p$ 为质数)或 exgcd 在 $O(\log p)$ 的复杂度内求的。但是如果要求 $1\sim n$ 的逆元，其实用不到 $O(n\log n)$。正如 $O...

AC 自动机是一种方便的多模式串匹配算法。基于字典树，用到了类似KMP的思维。 AC 自动机与 KMP 不同的是，AC 自动机可以同时匹配多个模式串，而复杂度不会达到太高。如果用 KMP 多次匹配字符串，复杂度就是 $O(k...

一、简介     KMP是由Knuth、Morris和Prat发明的字符串匹配算法，它的时间复杂度是均摊\(O(n+m)\)。其实用Hash也可以做到线性，只不过Hash存在极其微小的难以避免的冲突。于是就有了KMP。       KMP算法...

      尽管还没有接触到主席树的区间修改或其它可持久化结构，但是标记永久化这个东西在线段树上并不是一个鸡肋的东西，用在以常数大著称的线段树上可以有效地打分块的脸优化下放lazytag带来的较大常数。 ...

Miller-Rabin是一种高效的随机算法，用来检测一个数$ p$是否是素数，最坏时间复杂度为$\log^3 p$，正确率约为$1-4^{-k}$，$k$是检验次数。 一、来源 Miller-Rabin是由Miller和Rabin两个人根据费马小定理的逆定...

      fhq_treap是一个比较好写，扩展性强，并且可以完成splay所有操作的常数不大的数据结构。     fhq_treap不用旋转，它基于重构，也就是平衡树的合并和分裂。它可以通过一系列操作做到像splay一样...

     在学习笔记1中的矩阵乘法公式中，我们看出，每个位置的值都是多个积之和。那么如果矩阵可以加速这样的快速幂/乘法，那么就同理可以加速加法了。因此对于那些有递推关系的式子，我们就可以用矩阵加...

     矩阵是线性代数的内容，矩阵乘法和一般的乘法不同，矩阵A×B时要求A的列数=B的行数=k。算术结果：若$ C=A\times B,C_{xy}=\sum\limits _{i=1}^kA_{xi}\times B_{iy}$。      因此我们有...

刷模板记录：    线筛 期望时间:5分钟 最快:7分钟(2018.6.25)     LCA 倍增 期望时间:8分钟 最快:12分钟(2018.6.25)    LCA tarjan 期望时间:15分钟 最快22分钟(2018.6.25)    splay 期望时间:40分...