二分搜索虽然基本思想简单，但其细节却令人意外的抓狂（Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky）。这里我们来分析一下常见写法的坑。
两类不同的二分 二分有两类，一是找值，即判断某个值存不存在，二是找边界，前者比后者简单很多，以下是找值的典型写法（来自中文wiki百科）
int binary_search(const int arr[], int start, int end, int key) { int ret = -1; // 未搜索到数据返回-1下标 int mid; while (start <= end) { mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法 if (arr[mid] < key) start = mid + 1; else if (arr[mid] > key) end = mid - 1; else { // 最後檢測相等是因為多數搜尋狀況不是大於要不就小於 ret = mid; break; } } return ret; // 单一出口 } 对于找边界，有四种情况，如以下例子，查找数值5的四种边界
1 1 1 2 2 5 5 5 5 7 9 ^ 1 小于的最右元素 ^ 2 大于等于的最左元素 ^ 3 小于等于的最右元素 ^ 4 大于的最左元素 既然有四种边界，那就有四种写法。
在上一篇介绍了基础优化算法后，本篇介绍更复杂的内容。本篇的三大内容：FFT，NTT，分治除法。中文资料中我尚未发现有博客文章在介绍分治除法的，所以我就来写第一个介绍吧。
FFT (Schönhage–Strassen algorithm) FFT就是快速傅里叶变换的缩写，FFT这里不重点介绍，参见oiwiki中对FFT的介绍
用比较显浅且简要的方式来介绍的话，FFT可以在$O(nlogn)$时间里（注：严格来说应该是$O(nlognloglogn)$，论文链接在这，在274页7.8处开始证明）求出两个多项式的乘积，而大整数乘法就可以视为两个整数系数的多项式的积再处理进位即可。那这样就产生一个问题，如果这个大整数采用的基数base，且长度为n，那么多项式的积的最大值可能会达到$n(base-1)^2$，因为FFT采用浮点运算，那么这个最大值必须在double的精度内，所以如果采用万进制，那么很容易导致精度不足进而结果错误，另外，还有求单位复根时的误差也会让它提早出现结果错误。实际应用的时候，一般采用10进制来增加长度的上限。所以如果你的大整数采用压位表示，那么在运用FFT之前，要先做拆位拆成10进制。总之，因为浮点精度的问题，不建议在大整数实现里使用FFT，建议采用下文要介绍的NTT来代替。所以这里对FFT的优化不做介绍，重心放在NTT上。
NTT NTT就是快速数论变换，它和FFT很像，但它在整数域上做变换，具体数学介绍参见oiwiki中对NTT的介绍。由于没有浮点数参与，于是没有精度上的问题。
在上一篇介绍了基础算法后，本篇介绍算法级别的优化。本篇的三大内容：乘法优化，任意进制输入，任意进制输出。
乘法优化 这里要介绍的，是Karatsuba发现的分治法，我们假设要相乘的两个数，都有2n位，那么这两个数就可以分别表示为$a_1base^n+a_2, b_1base^n+b_2$，其中，$a_1,a_2,b_1,b_2$是n位的大整数，那么，它们的积就是
$$\begin{align} & (a_1base^n+a_2) \times (b_1base^n+b_2) \\
& = a_1b_1base^{2n} + (a_1b_2+a_2b_1)base^n + a_2b_2 \\
& = a_1b_1base^{2n} + ((a_1+a_2)(b_1+b_2)-a_1b_1-a_2b_2)base^n + a_2b_2 \end{align}$$
如果这样不够明显的话，我们用$c_1$代替$a_1b_1$，用$c_3$代替$a_2b_2$，得到
$c_1base^{2n} + ((a_1+a_2)(b_1+b_2)-c_1-c_3)base^n + c_3$
于是，这里一共有3次乘法，比起原来的4次暴力乘法减少了1次。而里面的乘法又可以进行递归优化，时间复杂度从$O(n^2)$下降到$O(n^{log_23})$约$O(n^{1.585})$
最近在编写大整数库的过程中，踩到不少的坑，于是把一些有用的细节准备写成文章做整理。如果你只是想直接查找并使用一个大整数库，那直接上GMP即可，如果是用在比赛，那直接用我的MiniBigInteger项目，如果你是想学习个中细节，那你可以坐下来细品。
所谓大整数，又叫高精度运算，就是运算对象是上千位甚至到百万位，总之远远超过内置数据类型的表示范围，这类数字都叫大整数。而C/C++的标准库里目前并没有大整数库，于是这个轮子被反复制造了无数个，不过在github上比较有质量的轮子并没有很多。本文除了介绍基础实现，主要还是介绍优化方法。
大整数的表示 大整数的表示方法最常见的有4种：
直接使用string 使用定长数组(仅适用于竞赛) 使用链表 使用变长线性表例如vector 直接用string的方式适合初学者，输入输出直观，但缺点也非常明显，因为计算时需要在字符与数值之间来回转换，浪费太多不必要的时间，效率会非常差。不过如果你是初学者，先用string表示法来写未尝不是个好主意。但有个细节就是，如果想要效率高，最好把string前后倒置调整为低位在前再做运算，这样速度和实现难度都会低一些。
至于使用链表，好处是变长容易，变短也不难，但性能比用string的更差还更难写，这里就不谈了，以下介绍使用数组的表示法
为了在数组里表示一个大整数，如果我们采用10进制，表示123456789，那很简单，例如这样：
Dancing Links缩写为DLX，其实在竞赛中并不常见，这次会讲这个是因为前一阵子搞拼图写了这个数据结构就顺便写(水)博客。
DLX的发明者是高德纳（Donald Knuth），就是那个传说中的《计算机程序设计艺术》（TAOCP）系列书的作者，这里对这个算法做一些比较直观的解释。
DLX面向的问题 DLX面向的问题是精确覆盖问题。何谓精确覆盖呢，来看以下这个表格，每一行是一个数组，数组有4个元素，每行的第一列是这个数组的名字
name a 0 0 0 1 b 1 0 0 1 c 1 1 0 0 d 1 0 1 0 e 0 1 1 1 f 0 0 1 0 g 0 1 0 1 我们的目标是，在这些集合里，挑出几个，例如我们挑a,b,c，那对应位置上的元素相加，于是得到 2 1 0 2。而我们的目标是，找到一个挑选的方法，使得相加得到 1 1 1 1 全是1。
例如说，选 d和g，那么相加正好得到 1 1 1 1 ，这就是其中一个解，这就是精确覆盖问题的直观感知。
回文树（EER Tree，Palindromic Tree），有点类似Trie，但它并不是匹配字符串的，很多人称之为回文自动机，但它一点也不像自动机，不过我还是按习惯的来，使用PAM为简称。为了表示一个回文，我们只表示一边的一个单链即可，这时就类似Trie。但不同之处是，回文区分奇数长度和偶数长度，所以这里我们使用两个根，分别来表示奇数长度和偶数长度。所以，在奇数根里，链ba表示aba，而在偶数根里的ba表示abba。
首先我们来直观地看看PAM的图形化，以下是字符串abcbbc的PAM
graph TD; linkStyle default interpolate basis subgraph root 0-.->1[-1] end subgraph node0 0-->6((bb)) 6-->7((cbbc)) end subgraph node1 1-->2((a)) 1-->3((b)) 1-->4((c)) 4-->5((bcb)) end 2-.->0 3-.->0 4-.->0 6-.->3 5-.->3 7-.->4 style 0 fill:#f9f style 1 fill:#f9f 实线方向就是子节点方向，虚线是fail指针，指向这个节点最长的回文后缀节点。图有点乱，但又不希望画得过于简单导致说不清楚，将就一下吧。
后缀自动机（SAM），可以结合前文的AC自动机一起理解，所谓后缀自动机，就是把一个字符串的所有后缀构造AC自动机，即只匹配其后缀的自动机。但是作为一个字符串的所有后缀，与一般的AC自动机有些不一样的性质，直接构造AC自动机，节点数是 $O(n^2)$，而SAM则对重复的节点合并了，可以让节点数大幅下降到 $O(n)$。
首先我们来直观地看看SAM的图形化，以下是字符串abcac的SAM
graph LR; linkStyle default interpolate basis 0((0))--a-->1 1--b-->2 2--c-->3 3--a-->4 4--c-->5((5)) 0--c-->6(1) 0--b-->2 1--c-->5 6--a-->4 4-.->1 5-.->6 3-.->6 1-.->0 2-.->0 6-.->0 style 0 fill:#f9f style 5 fill:#f9f 实线方向就是匹配方向，虚线与AC自动机中的失败指针非常像，在SAM里称为link指针。
听到AC自动机很多人第一次听到的反应往往是很兴奋的。但其实并不是你们想的那种东西。它的全称是Aho-Corasick algorithm，另外，自动机的英文是Automaton，所以AC自动机即 AC Automaton。为了解释这个算法，首先我们来回顾KMP，你需要很理解KMP的原理，不然看后面的内容就会变得妙不可读。
KMP自动机 本质上KMP其实就是一种自动机。这次我们改用自动机的形式来理解。所谓自动机，一般指的是确定有限状态自动机，你可以看作一个黑箱，每次输入一个数据，它就会改变它的内部状态，并有相应的输出。如果你知道Trie，那么它其实就是一个典型的自动机。我们还是拿字符串abacabab作为例子，如果是生成next数组，结果如下：
string a b a c a b a b \0 next -1 0 0 1 0 1 2 3 2 为了方便变成自动机的方式理解，我们把这个改成有向图
graph LR; linkStyle default interpolate basis 0[Start]--a-->00[1] 00--b-->1[2] 1--a-->2[3] 2--c-->3[4] 3--a-->4[5] 4--b-->5[6] 5--a-->6[7] 6--b-->7[8] 00-.->0 1-.->0 2-.->00 3-.->0 4-.->00 5-.->1 6-.->2 %%7[b]-.->3[c] style 0 fill:#f9f,stroke-dasharray: 5, 5 style 7 fill:#f9f,stroke-dasharray: 5, 5
这次主要介绍伪随机数生成算法，顺便介绍一个在2018-2019年的伪随机数研究成果，就是 xoshiro/xoroshiro 随机数生成算法。
历史 在较早的时候，甚至到现在，伪随机数的生成元老级别算法“线性同余伪随机数生成算法”可谓无处不在，像现在的C/C++的rand函数就是使用线性同余实现的伪随机数生成。所谓的线性同余法，就是这个迭代方程 $S_n = (aS_{n-1} + c)\mod m$，其中，$S_0$ 称为这个随机序列的种子，a,c,m是三个常数，不过这三个数不能随意选，m的大小决定随机数的周期，最大周期等于m，为了便于在计算机里实现，通常m选取$2^{32}$或$2^{64}$。在m已经确定为这两的时候，为了让周期尽可能大，常数a,c还至少要满足以下条件：
若 c 非 0，那么 c 与 m 互质；若 c 为 0，那么 a 与 m 互质 m 所有的素因子均能整除 a-1 若 m 是4的倍数，那么 a-1 也是 4 的倍数 a 和 c 都是正整数且小于 m 一些典型的常数取值可以参见wiki上的线性同余条目。
更高的需求 我们之所以使用线性同余，就是因为它实现简单，在对随机数质量要求较低的时候，例如用来作为treap的随机数，那么线性同余完全够用，但建议不要使用rand，因为在windows下不少编译器的最大值太小了，导致效果下降，自己写一个用参数a=69069,c=1,m=2^32比rand好，我在那篇关于treap的文章就是用了这组参数。线性同余法最大的缺陷是低位随机性特别差，如果使用类似next() % k的方式来获得区间在$[0,k-1]$的随机数，那么当线性同余迭代方程的m是2的幂且k也是2的幂的时候，灾难就发生了，特别地当k是2的时候，你将得到一个0101的循环序列。为了避免这种情况，通常会取线性同余结果的高位，而且低位去掉得越多，%2的周期就越长。例如结果是64位，取高32位作为最终结果，那么%2的周期就是 $2^{33}$ ，但这样会导致有效位减少，而且问题也没有根本地解决。另一种解决办法是选取一个素数作为m，例如2147483647正是一个素数，但如此一来，线性同余的计算速度就会慢不少，周期也没有前一个的长。两种基本实现如下：
可持久化权值线段树，wiki上指出引入者名字叫黃嘉泰，名字缩写正好是某位主席名字，所以又叫做主席树。而本篇先介绍可持久化线段树，阅读本篇前你需要先了解线段树
概念 所谓的可持久化，意思是你能得到所有的历史版本，为了达到这个效果，当然可以每次修改的时候，先整体复制再修改，结果自然就是会爆内存。而事实上，由于每次修改最多改一条链，而其它分支可以重用。我们先拿链表做例子，如果有个链表内容是 1->2->3->4->5 ，现在我们把3修改成6，得到 1->2->6->4->5 ，但是后面的元素没有改动，所以我们可以把后面的元素直接重叠在一起使用，如下图：
graph LR; 1-->2 2-->3 3-->4 4-->5 1'-->2' 2'-->6 6-->4 这样，完全可以当成两条不同的链表使用，同时节省空间。而可持久化线段树做法与这一样，就是没变的部分还使用原来节点，所以这个实现不能使用之前介绍的堆式储存，要和平衡树一样动态开节点。
数据结构 假设我们的数据是以下这样
下标 1 2 3 4 数据 1 0 5 2 构建线段树后结果如下
graph TD; 1,4:8-->1,2:1 1,4:8-->3,4:7 1,2:1-->1,1:1 1,2:1-->2,2:0 3,4:7-->3,3:5 3,4:7-->4,4:2 冒号前面的两个数表示一条线段，冒号后表示的是数据，这个数据表示的是这个区间的和。
然后我们要把第3个元素从5改为1，构造第二棵线段树，首先复制一个root，包括儿子的指向也复制，得到
graph TD; 1,4:8-->1,2:1 1,4:8-->3,4:7 1,2:1-->1,1:1 1,2:1-->2,2:0 3,4:7-->3,3:5 3,4:7-->4,4:2 1,4':8-->1,2:1 1,4':8-->3,4:7