detect

FFT是一种可以在O(n∗logn)O(n*log_n)O(n∗logn​)的优秀时间复杂度里，求出两个多项式乘积的优秀算法。 首先，我们如何表示一个（n−1）（n-1）（n−1）次多项式？ 用每一项的系数来表示 用n个点的坐标来表示 所以算两个多项式乘积时，如果暴力计算系数，是O(n2)O(n^2)O(n2)的。 但是如果我们有这两个已知多项式的点的表达式，那么我们只需要O(n)O(n)O(n)的时间就可以得到带求多项式的点表达式。 不幸的是，为了得到两个多项式的n个点坐标，在横坐标随记下我们仍需要O(n2)O(n^2)O(n2)的时间来完成。 所以有没有什么办法可以优化找点的过程了。 以为名叫傅里叶的牛人发现了复数可以完美解决这个问题。 具体来说，我们再复数坐标戏中引入单位元（类比三角函数），因为复数有个性质，两复数乘积的几何意义是模长相乘，辐角相加。 因为我们取得点在单位圆上，于是同一个复数的nnn次乘积在几何意义上表现为辐角的成倍增长。 前方高能，我们开始搞事情了。 设带求多项式为F(x) 我们按照多项式次数的就分成两节。 即F(x)=FL(x2)+x∗FR(x2） ...

（p.s: code是真的短） 从头开始的详细版见WiKi 主要的难点都在后缀边和点的划分上。 重新声明一下定义: 我们按照这个字串在原串中每一个出现的最后一位的位置集合为一个点，即一个点里可以包含多个字串，我们钦定每个点中最长的字串长度为lenilen_ileni​。 后缀边 按照点的集合定义，后缀边其实是把这些点按照集合包含关系连了起来（只会连所有包含关系中len最小的那个点），即成一棵树。 然后就好办了啊 建立SAM算法流程简析 首先建立前缀的节点，集合只有前缀本身 从上一个前缀节点开始向上搜索看有没有点有新加入字符的正向连边。（注意正向连边图是一个DAG） 分三种情况： 若全没有，则该字符没出现过，fa->root即可 找到存在p，设q为p的该字符的对应点， 若 len[p]+1==len[q]len[p]+1==len[q]len[p]+1==len[q] ，因为p是原来串的最长可以跟字符s的点，原串与新串差1，如果len也差1，那么q必定是包含新串最长的点。 现在没发再特判了，需要新建立一个点来解决问题。 这个点继承q点后面 ...

之前写过一篇按权值的fhq，可以解决查询前驱后继，第k大等操作。 不过如果我们把fhq的特性转移到数列上，即类比线段树储存sum，标记之内，那么又是一个新毒瘤数据结构了。 补：（一些对FHQ的理解） 一共只有n个节点，不像线段树有2n个左右，因为fhq节点的左右儿子都是直接的节点（而线段树需要辅助节点），同时如果是对序数fhq，中序遍历就是当前数组，而对权值fhq，中序遍历是从小到大的顺序。 split的时候，两个取址的参数是分别两个分裂子树的root，注意，他们是完全分割的两个东西，并没有直接联系，第一层分裂完后，下一个该归到同一个分裂fhq的作为它的左右儿子。 一些注意事项： FHQ的正确性基于满足中序遍历和堆性质的树的形态是固定的。 pushdown操作如果要改变子树形态或者siz大小，需要小从把标记推完后，再进行操作。 毒瘤板题传送门 我们知道线段树可以实现区间和，区间更改，最大子段和等操作，但此题还要求加入一串数、删除一串数、翻转一串数的操作。 现在思考一下如何用fhq解决以上问题。 fhq本身由插入顺序决定相对位置(因为其本身是一棵二叉搜索树 ...

板题大赏。 板题1 凸包 我们先选最左下的一个点，它一定在凸包上。 于是将其他的点按照与左下点的极角排序，用单调队列维护外凸即可。（因为凸包的外边按照顺序一定是极角依次增大） （p.s 对于此题，在一条线上的点不会影响最后答案，可以不用在极角的基础上按照长度排序） 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>using namespace std;int n,m;const int M=1e5+5;const double eps=1e-9;inline int sig(double x){ if(fabs(x)<eps) return 0; else return x>0?1:-1;}struct point{ double x,y; point(double _x=0.0,double _y=0.0){ x=_x,y=_y; & ...

莫比乌斯反演 形式 1 （卷积法证 如果有 F(x)=∑d∣xf(d)F(x)=\sum\limits_{d|x}f(d) F(x)=d∣x∑​f(d) 有如下反演： f(x)=∑d∣xμ(d)f(xd)f(x)=\sum\limits_{d|x}\mu(d)f(\frac{x}{d}) f(x)=d∣x∑​μ(d)f(dx​) 证明如下（用狄利克雷卷积易证）： F=f∗1F=f*1 F=f∗1 F∗μ=f∗1∗uF*\mu=f*{1*u} F∗μ=f∗1∗u F∗μ=f∗EF*\mu=f*E F∗μ=f∗E f=F∗μf=F*\mu f=F∗μ 证毕。 形式2 （带入法证 莫比乌斯反演第二种形式 F(n)=∑n∣df(d)−−>>f(n)=∑n∣dμ(dn)F(d)F(n)=\sum_{n|d}f(d)-->>f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d) F(n)=n∣d∑​f(d)−−>>f(n)=n∣d∑​μ(nd​)F(d) 证明如下： 将F(d)F(d)F(d)带入右边式子，并设k=dnk=\frac{d} ...

一句话总结杜教筛： 综合起来，杜教筛算法可以概况为：用狄利克雷卷积构造递推式，编程时用整除分块和线性筛优化，算法复杂度达到了O(n23)O(n^{\frac{2}{3}})O(n32​)。 只要给你的函数的卷积和函数可以方便的表示出来且好计算，那么杜教筛就有用武之地。 现在开始推倒杜教筛的过程 要求函数：f(x)f(x)f(x)的前缀和 s(x)s(x)s(x) 我们设两个函数为h(x)g(x)h(x) g(x)h(x)g(x)有h(x)=f(x)∗g(x)h(x)=f(x)*g(x)h(x)=f(x)∗g(x) ∑i=1nh(x)=∑i=1n∑j∣if(ij)g(j)\sum_{i=1}^nh(x)=\sum_{i=1}^n\sum_{j|i}f(\frac{i}{j})g(j) i=1∑n​h(x)=i=1∑n​j∣i∑​f(ji​)g(j) ∑i=1nh(x)=∑j=1n∑j∣inf(ij)g(j)\sum_{i=1}^nh(x)=\sum_{j=1}^n\sum_{j|i}^nf(\frac{i}{j})g(j) i=1∑n​h(x)=j=1∑n​j∣i∑n​f(ji​)g ...

Ac自动机 它由三个部分组成： 建立字典树 找出字典树上每个点的fail 跑匹配串来搞事情 建立字典树 就是表面意思，我们把所有待匹配串来建一个字典树 寻找fail指针 这个和kmp类似，如果一段前缀和另外一段后缀重合，那么这段区间就不需要再来一个个匹配。 我们考虑用bfs来求fail指针（最大重合部分的指针）： 对于一个点u，现在目标求所有u的子节点的fail（注意顺带搞一下空节点，对后来的模式串匹配过程有帮助） 若存在u的连边v。 那么v的fail即为u的fail的v’儿子 若不存在u的连边v。 既然不存在这个点，那我们手动添加虚点，保证原来的字典树上所有点都有所有的儿子，这样将情况转回到1去。 匹配 我们沿着字典树跑一边匹配串 每跑一个点，都沿着fail把所有可以fail的跳一遍，这些点都是可到的。 然后接着一直跑到底。（注意如果跑出字典树的边界也无妨，因为虚点的连边又将其引回字典树上） 板题1 AC自动机（简单版） 此题只要求出不出现，于是查询时不断打标记，保证同一个点不走两遍即可 code 12345678910111213141516 ...

无源汇有上下界可行流 我们先强行给每条边把底线塞满，但是这必然导致出入流不等，现在我们要寻找一种流法将这差值补满。 新建源点和汇点，原图上连r−lr-lr−l的流量，每个点多出或少的流量从源点接入或接出到汇点。再从源点到汇点跑网络流最大流，如果能做到出流等于入流，那么说明可以构造出一种流法补全原来出入流不对等的方案。 有源汇有上下界可行流 区别仅是出点和入点这两个点不用满足出入流平衡，那么从汇点连无线流量到源点（不是上面定义的超级源汇点），即可。 有源汇有上下界最大流 首先跑一遍有源汇有上下界可行流，然后关注残余网络，s->t图中剩下的流量是我们可以人为安排的，所以再从原来的源点到汇点来一次的最大流即是答案。 由于S没有入边，而T没有出边，因此增广路不会经过S,T也就不会导致约束条件失效（即始终满足流量平衡）。 （最后答案由两部分构成，之前的可行流flow1，和之后的增广流flow2的和。注意到第一次求可行流时，已经有了一条s->t的流量为flow1的边，所以直接再自从s->t跑一次最大流就是flow1+flow2） 1234567891011121314151617 ...

前置知识：FMT 或卷积 FMT FMT(x)=∑i∣xxiFMT(x)=\sum_{i|x}x_i FMT(x)=i∣x∑​xi​ 123void FMT(int *A){ for(int i=0;i<=n;i++) for(int j=0;j<=up;j++) if(j&(1<<i)) (A[j]+=A[j^(1<<i)])%=mod;} IFMT FMT的逆运算。 123void IFMT(int *A){ for(int i=0;i<=n;i++) for(int j=0;j<=up;j++) if(j&(1<<i)) (A[j]-=A[j^(1<<i)])%=mod;} 或卷积 C=A∣orB −>Ci=∑j∣k==iAjBkC=A|_{or}B \ ->C_i=\sum_{j|k==i}A_jB_k C=A∣or​B −>Ci​=j∣k==i∑​Aj​Bk​ 有 FMT(C)=FMT(A)∗FMT(B)FMT(C)=FMT(A) ...

生成函数 前置知识 数学功底（包括但不限于基本的积分求导） NTT与多项式全家桶 引入 思考 有2个红球，3个黑球，5个白球（同色球完全相同），从中任 取6个球。 有多少种不同的取法？ 如果还要将取出的球排成一排，有多少种不同的排法？ 问题一的答案是多项式 F(x)=(1+x+x2)(1+x+x2+x3)(1+x+x2+x3+x4+x5)F(x)=(1+x+x^2)(1+x+x^2+x^3)(1+x+x^2+x^3+x^4+x^5)F(x)=(1+x+x2)(1+x+x2+x3)(1+x+x2+x3+x4+x5) 的[x6]F(x)[x^6]F(x)[x6]F(x) 从卷积形式思考很容易。 但是如何思考问题2？ 我们从答案考虑如果选了a,b,ca,b,ca,b,c个，那么答案为(a+b+c)!a!b!c!\frac{(a+b+c)!}{a!b!c!}a!b!c!(a+b+c)!​，那么我们对多项式分配一下得到： G(x)=(1+x+x22!)(1+x+x22!+x33!)(1+x+x22!+x33!+x44!)G(x)=(1+x+\frac{x^2}{2!})(1+ ...