Nim 游戏的规则是这样的：地上有n堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。题 我们从基本的思路开始 以下我们为先手 首先，我们假设面前只…

线段树NB 李超线段树:维护最优势直线(选定x的时候y最大/最小的线段) 下面我们维护最大值 开一棵x范围的线段树,然后线段树的每个节点记录这个区间中点最高的线段(x = \frac {(l + r)} 2) 维护时考虑…

本文来自原博客，最后更新时间为2019年7月，请知悉 基本数论算法 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ... 这就是优美的卡特兰数的前10项 不要把它和斐波拉契数列搞混了…

本文来自原博客，最后一次更新时间为2019年7月，请知悉 基本数论算法 快速幂 放在这里，防止大佬突然大脑短路 1. 非递归 long long power(int a, int n, int k){ long long…

下标从1开始 引子 后缀自动机（SAM），即一个接受字符串所有后缀的最小DFA（确定性有限状态自动机），可以解决很多字符串相关的问题。 SAM最简单、也最重要的性质是，它包含关于字符串的所有子串的信息。依次记录任意从初始…

还是不把数据结构的总结文章的标题用\<算法>这种名字了...... 维基百科英文版的，这里的内容很多参考了那边：这里 （啊那个中文版太扯了） 左偏树满足堆结构，特点：可合并。声明：可并堆不止左偏树。 左偏树…

注意了，LCT\not=动态树 当然没啥 建议这篇文章看两遍以后再去看看其他文章，反过来也OK，因为码风太毒瘤了... 当然指针的写法用来理解思想是很棒的 前言 树链剖分用的是重链剖分，我们把一棵树搞成了一条链，然后用一…

一直不太喜欢数论呢 预警：这篇文章公式里面的1请看做为\mathbf 1，是常数函数 一些定义：（不严谨的话以后有时间再改吧） 数论函数：定义域为整数的函数；（理论上数论函数好像是要粗体或者拉丁字母来着？比如\mathb…

突然发现树链剖分应该不算算法？ 树链剖分：树\to链，方法：DFS序（dfn）。 前置问题： 将树从x到y结点最短路径上所有节点的值都加上z、求树从x到y结点最短路径上所有节点的值之和，在线 很好做对吧，树上差分，复杂度…

后缀数组是一个把所有后缀进行了排序的数组，如ababa这个字符串的后缀数组就是[5, 3, 1, 4, 2]，对应后缀：a, aba, ababa, ba, bab s[i]字符串，从1开始 sa[i]（长度为k的）排名…