玄学算法/精彩DS总结 Lud

## $51.Primitive\ Root$ 原根是一个好东西啊。 ### $1.$定义及相关性质 阶：满足$a^m\equiv 1 \pmod p$的最小$m$，其中$(a,p)=1$。记$ord_p(a)=m_{\min}$。 原根：满足$ord_p(a)=\varphi(p)$的$a$。 **原根的性质**：每个数$p$有$\varphi(\varphi(p))$个原根；每个原根$g$的$g,g^1,\cdots,g^{\varphi(p)}$在$\bmod\ p$意义下构成了一个**既约剩余系**。第二个性质十分重要。 ### $2.$求原根 这并不是很重要，因此可以直接暴力枚举原根。 ### $3.k$次剩余 求 $$x^k=n\pmod p$$ 下的$x$，这里我们暂定$p$是质数。听说当$n=1$的时候这个$x$也叫模$p$意义下的$k$次单位根。 首先我们先离散对数一下，取$log_g$之后会变成 $$wk=r\pmod{\varphi(p)=p-1}$$ 设$w=log_gx,r=log_gn$，那么$x=g^w$，$n=g^r$，于是$r$可以直接$BSGS$求出。 问题转变为$wk=r\pmod{p-1}$，直接用扩欧解一下就可以了。 ### $4.$模意义下的$2^n$次单位根 其实很简单，因为$g^{p-1}=1$,$\omega_{2^n}=g^\frac{p-1} {2^n}$。 这也解释了为什么$NTT$模数能卷积的范围是$2^m$，其中$p=x2^m+1$，且$x\&1=1$。 ## $52.EX\ Baby-Step-Gaint-Step$ 扩展$BSGS$主要用来解决$BSGS$的模数不互质的问题。 ## $53.Computational\ Geometry$ 计算几何是一个挺毒的东西。一般来说，我们较少地运用解析几何中的内容，而较多地使用线性代数方面的知识。 这个东西本来应该开一个$slide$，但是没有时间了，就写到博客里。 ### 叉积/外积 叉积是$OI$中计算几何的核心内容。定义两个二维向量的叉积$\vec{a}\times\vec{b}=x_1y_2-x_2y_1$。实际上叉积的定义基于行列式，而二维行列式的值就是如此。 **叉积的计算式是**$\vec a\times \vec b=|a||b|\sin\theta$。根据这个式子，我们可以判断两个向量的方向。当$\vec{a}\times\vec{b}>0$时，$\theta>0$，也就是$\vec b$在$\vec a$逆时针方向。 **叉积的几何意义是以两个向量共出端，且作为邻边形成的平行四边形的 _有向_ 面积**。如果要搞出个正的，就要按极角排序，角度大的那个是$(x_2,y_2)$（也就是$1$在$2$顺时针方向）。点$3$是原点。 由这个公式，在我们要求一大堆点构成的所有三角形面积的时候，我们可以先极角排序（$atan2$/固定一点之后按叉积排序）,然后计算就可以累前缀和了，因为这样叉积始终为正。 接下来的大部分内容都建立在叉积上。 ## 点与线 ### 点积 ~~模模$\sout{\rm cosine}$！~~ 点积的几何意义是一个向量在另一个向量上的投影乘上第二个向量的模长。 ### $atan2$ 这个东西是计算方位角的函数。$atan2(y,x)$相当于$(x,y)$的方位角。 譬如$atan2(1,1)=\frac{\pi}4,atan2(1,0)=\frac{\pi}2$。 ### 转角 一个点$(x,y)$逆时针旋转$\theta$，会变成$(x\cos\theta-y\sin\theta,y\cos\theta+x\sin\theta)$。 ### 点到直线的距离 解析几何的公式是$\frac{Ax_0+By_0+C}{\sqrt{A^2+B^2}}$，就是精度不是很优秀。 设$X$是点，$A$是向量出端。 实际上我们可以用一个向量确定一个直线，然后作向量$\overrightarrow{AX}$，与$\overrightarrow{AB}$叉一下得到的结果再除以$\vert\overrightarrow{AB}\vert$就是距离了。这个运用到了叉积的几何意义。 ### 点到直线的投影及其坐标 点到直线的投影长度就是拿向量的出端给它作个向量然后直接作点积。设$X$是点，$C$是投影点，$A$是向量出端。 要求坐标的话，求出$\overrightarrow{AB}\cdot\overrightarrow{AB}=|AB||AB|$，就求出了$\frac{|AC|}{|AB|}$。然后把这个模长比乘上$\overrightarrow{AB}$，就得到了向量$\overrightarrow{AC}$。再加上$A$的坐标，就得到了$C$的坐标。 ### 直线/线段判交及其交点 其实解析几何的方法很快，但是有可能爆精度$\cdots\cdots$不过如果你只知道$k,b$的话，其实还是非常方便的。 面积比$\to$高比$\to$相似转化为长度比$\to$交点坐标。 上面这个东西看着就很玄学。我们详细地讲一下它的几何意义。 设$AB,CD$是两条直线，$O$是交点。其中$ABCD$坐标已知。 我们先求出$S_{\triangle ABC},S_{\triangle ABD}$。显然由于底边相等，面积比就变成了两个高的比。 但又有一个显然的相似，就是$\triangle COH\sim\triangle DOH'$，其中$H,H'$分别指$ABC,ABD$底边为$AB$的高。那么两个高的比就转化为$CO:OD$。 然后因为我们知道$\overrightarrow{CD}$和$C$，乘一下比例就得到了$O$坐标。 注意叉积为$0$两条直线不相交。 接下来考虑直线与线段判交。设$C,D$为线段端点。 这个就按老套路，$A,B$各自朝$C,D$连向量，算一下两个三角形的有向面积是否同号，如果同号就不相交。 最后考虑线段与线段判交。 这个我们可以先假设某条线段是直线，然后与另一条线段判交。如果相交，再把另一条线段设为直线，与这条线段判交。如果都相交那么就是真的相交。 算交点与直线交点类似。 ## 多边形 ### 求多边形面积 用叉积把多边形化为三角形很方便。 先考虑凸多边形，随便定一个点$A$为起始点，然后逆时针开始扫。 找到相邻两个点$BC$，$\frac{\overrightarrow{AB}\times\overrightarrow{AC}}2$就是$S_{\triangle ABC}$。然后一个一个扫过去就求出来了。 然后如果有凹的也无所谓，它是负的就直接减掉，你会发现最后求出来的和还是对的，正好容斥完了。**注意枚举点的顺序不能变**。 ### 点与多边形的位置关系 我直接搬$Hometown$的。 假想有一条从该点出发，水平向右的射线。 依次枚举多边形相邻两 点，统计这两个点的连边穿过这条射线的次数。 若逆时针穿过，则计数器$+1$，顺时针穿过时，计数器$-1$。 如果计数器为$0$，则点在多边形外部，否则在多边形内部。 注意判断点在多边形上的情况。 对于凸包，有一种更快速的$O(\log n)$的算法。 首先我们把整个凸包移位（下面讲了），然后可以发现每个点也代表了一个从$(0,0)$连过来的向量。于是我们在凸包上二分，找到角度最小的又比它大的那个向量（点）$A$，那么下一个点$B$肯定比它小（因为我们构建凸包的时候极角是从大到小的）。于是我们让$\overrightarrow{AX}\times\overrightarrow{AB}$，如果$\ge 0$就在凸包内（或在边界上）。注意特判角度比最大角要大，最小角要小的情况。 ### 凸包 先假设给定了点集。 我们把所有点按$x$坐标从小到大排序，然后从左开始，比较$\overrightarrow{s[tp-1]s[tp]},\overrightarrow{s[tp]X}$这两个向量，$X$就是当前枚举到的点。 如果两个向量叉出来的结果$>0$，那么意味着$s[tp]$不在上凸壳上，要把它弹掉。这样就求出了上凸壳，再反过来做一遍（或者设叉积$<0$弹栈然后再正着做一遍）就求出了下凸壳。 一般情况下，如果要对凸包进行与向量相关的查询，最好把最左边的点定位到$(0,0)$，所有点也要跟着移动，查询的时候让向量减去最左边的点的原坐标（画一下图可以发现这样是没问题的）就可以做了。 ### 动态凸包 我们对上凸壳和下凸壳分别维护一个以$x$为键值的$set$，每次插入一个点时在两个$set$上$lower\_bound$找到位置，然后叉积判一下点是否在凸包内，如果在就啥都不用干，不在就看它更新上或者下（或者一起）凸壳，往左往右扫，看它会把哪些点删掉，由于斜率是单调的，直接枚举两个相邻点，然后用第一个点连两个向量（这个点和枚举的第二个点），叉一下发现它在里面了就不用继续了。 这个算法的时间复杂度是均摊$O(m\log n)$，而且可以在过程中顺便维护周长、面积等信息，可以做到$O(1)$查询。 ### 闵可夫斯基和$(Minkowski\ Sum)$ 闵可夫斯基和的定义是$C=\{a+b,a\in A,b\in B\}$的凸包，其中，$A,B,C$都是点集。 形象一点的可以看$FlashHu,xzy$的博客。 通过观察，我们发现闵可夫斯基和上的边都是原来$A,B$凸包上的边，而且它们连接的顺序是按极角排序了的。 那么我们就把两个凸包上的所有边看成向量（逆时针），然后把所有边合在一起排序，按极角一个个插入就可以了。这个实现可以直接用两个指针扫，因为你凸包里求的顶点已经按极角排序了。~~据说这玩意叫归并排序？~~ 起点就直接找两个凸包最左边的点，这两个点加起来的点一定在闵可夫斯基和上。 这个东西口胡起来很简单，实现起来很毒。主要原因是一大堆向量根本想不清。 为了方便，我们求完闵可夫斯基和后直接再求一遍凸包，就判掉了一些共线/同点的~~JB~~情况。 ### 旋转卡壳 关于这个名词的十六种读法我们在此不作讨论。 这个东西用于求凸包直径，或者到某条边的最远点。 具体来说就是因为你求出来的凸包已经很有各种意义上的单调性了，就直接拿$two-pointer$扫一下就可以了。 实现细节还不是很清晰，要再问问。 ### 半平面交 似乎是线性规划的一种解法。~~但似乎不会用来求解线性规划~~ 好像是维护一个$deque$然后判交点位置来弹队列啥的，不想学了。 ## 圆 ## 其它 ### 自适应辛普森积分 简单来说就是用个二次函数拟合一下原函数，然后求一下区间的积分。 $$\int_{l}^rf(x)\mathrm{d}x\approx\frac{(r-l)(f(l)+f(r)+4f(\frac{l+r}2))}6$$ 如果$[l,mid],[mid+1,r]$的积分值的和与$[l,r]$的积分值精度误差比较小，就直接返回；否则就继续往两个区间递归。 ## $54.Captain\ Mo's\ Algorithm$ 本来觉得莫队算法太沙雕了不想写，现在看来不写就会忘，于是赶紧来补一下。 莫队算法是一种离线算法，主要用于处理在单点贡献很好计算时的一类查询问题。 ### $1.$序列莫队 在没有修改的情况下，莫队能够在$O(n\sqrt q+q\log q)$的时间复杂度下解决问题。 具体来说，就是你发现加入把所有询问按左端点排序，然后用指针去跳右端点算每个询问的答案。然后你发现这样是$O(nq)$的。 于是可以用分块优化这个过程。很妙的是，其把左端点分块，也就是排序后，如果两个点所属块相同，那么就按右端点排序，否则按左端点排序。 这样的话，$l$的移动次数最多为询问数$\times$块的大小，即$O(qB)$，$r$的移动次数最多为块的个数$\times$总区间大小，即$O(\frac{n^2}B)$。于是总复杂度是$O(qB+\frac{n^2}B)$。这好像是个对勾函数，当$B=\sqrt{\frac{n^2}q}=\frac n{\sqrt q}$时，函数有极小值。 注意初始时让$l=1,r=0$，这样能方便地算贡献。至于为啥你写的时候就知道了。 ### $2.$回滚莫队 当加入很方便，删除算贡献不方便的时候，我们就要用到回滚莫队了。 其实很简单，就是用个栈维护左指针的移动，移动完一个询问就直接回去就可以了。注意到下一个块的时候我们可以直接清空答案，然后重新开始移动$r$。 有些细节比较恶心，注意为了方便，同块答案直接计算，还要注意$l,r$的位置，栈只与$l$有关与$r$无关，反正一堆细节。 ### $3.$一些骚操作 ### 常数优化 我们知道，莫队的右指针是在不断跳动的，然而我们左端点每次换块时，如果$r$还是递增的，那么$r$就要先移回来再移回去，白白增加了常数。因此我们在排序时，奇块让$r$递增，偶块让$r$递减，可以让常数$\div 2$。 ### 莫队套分块 具体来说，就是我们知道莫队的查询是$O(1)$的，而修改是与莫队维护的数据结构相关的。然而莫队移动并修改的复杂度是$O(qB+\frac{n^2}B)$的，如果套个数据结构会变成喜闻乐见的$O(\sqrt q\log n)$。而有时候我们的$n,q$比较大，是不资瓷这样的操作的。于是我们可以优化修改的复杂度，让它变成$O(1)$，然后在每次查询时利用分块来查一遍答案，复杂度就变成了$O(n\sqrt q+q\sqrt n)$（此处默认分块的块大小是$\sqrt n$）。 注意这里两个分块的块大小是独立的，没必要均在一起算。 ### 调块大小 这个套路我去年就学过了$\cdots\cdots$就是直接让几个复杂度相等，取到的$B$是多少就是多少。 ### 按时间分块 在$EI(EntropyIncreaser)$的博客里学到了一种处理时间的骚操作。 ## $55.Prufer\ Sequence$ $Prufer$序是一个无根树计数的巧妙工具，它能把有关树结构的限制转换到序列上来。 ### $1.$定义 如果给定无根树，我们这么求$Prufer$序。 找到树叶子编号最小的结点，然后把它的父亲加入$Prufer$序，然后把这个叶子删掉。当只剩下两个结点时结束，因此$Prufer$序长度为$n-2$。 给定$Prufer$序同理，找到点集中$Prufer$序的$\rm mex$，然后取出最前面的元素，将它们两个连边即可。全部做完**点集**还剩下两个点，将它们连边。 用$set$实现比较简单，时间复杂度$O(n\log n)$。 ### $2.$性质 首先$Prufer$序的任何一个数都可以是任何结点，因此$n$个点有标号无根树的个数是$n^{n-2}$。 其次每个结点在$Prufer$序中的出现次数就是$dgr[u]-1$。 ## $56.Miller-Rabin$ $Miller-Rabin$是一个可以在$O(k\log n)$的时间复杂度内探测一个数是否是质数的测试算法。其中$k$是测试次数。 首先根据费马小定理，对于模$p$在剩余类环中的任何一个数$x$，当$p$是质数的时候$x^{p-1}\equiv 1\pmod p$。 我们可以根据这个筛掉一部分比较菜的合数。但卡迈克尔数就很厉害，它筛不掉。 那么我们还有一个二次探测，就是当$x^2\equiv1$的时候，$x=1/p-1$。如果不是就是合数。如果不等于$1$，我们可以让$x^4$再探测一次。依次类推。 实现可以写得骚一点，先把$p-1$的$2$的次幂提出来，然后从小到大探测，最后的那个数就是$x^{p-1}$，再看看它是不是$1$就可以了。这样每次好像有$\frac14$的概率错，多选几个$x$就可以了。 ## $57.KMP$ 求的是前缀$border$。 考虑上一次求出来的$border$的右端在$i$，如果$i+1$与当前枚举位置不匹配，我们就看看$border$的$border$的下一位能不能匹配，以此类推。 最后能匹配的，当前位的$border$长度就是那个长度$+1$。 （$UPD$：奶的真好，正是这个东西葬送了我的$OI$生涯。）