如果我不知道把一些东西放在哪里,那就放在这里吧

实际上是一些trick

Posted by ShanLunjiaJian's Blog on November 16, 2021

呃。


不知道干什么的时候

(gf)不知道干什么的时候你就求个导。

(任何情况下)不知道干什么的时候你就打个表。

(线性规划)不知道干什么的时候你就对偶一下。

(数数)不知道干什么的时候你就容斥一下。

(数数)不知道干什么的时候你就看看是不是独立的。

(任何情况下)不知道干什么的时候你就枚举一个方向。

(主要是ds)不知道干什么的时候你就把时间维画出来。

(博弈论)不知道干什么的时候你就考虑一个胜负确定的无穷集合。


树上动态斯坦纳树边权和

对于一个点集,按dfn排序,相邻dis之和(转一圈)就是斯坦纳树边权和的两倍。

可以用set维护,更牛逼的方法是veb。


毛毛虫修改查询

make hld great again!

定义树上一条链的毛毛虫是说这条链加上它的邻接点。支持链/子树/毛毛虫 加/求和,呃实际上感觉可以做任意交换并结合的信息。你说为什么交换并结合?因为子树或者毛毛虫上的信息不结合你难道强行规定顺序/jy

考虑重链剖分之后,每条链走三遍来分配编号 :

  • 第一遍从上到下分配重链。

  • 第二遍从上到下分配重链上每个点的所有轻儿子。这导致除了以$1$为根的链,别的链在第一步的时候,链头是已经分配完了的,它和重链剩下的部分不连续,需要特殊处理。

  • 第三遍从上到下递归重链上每个点的所有轻儿子的重链。

how it works?

  • 对于链,显然。

  • 对于毛毛虫,每次往上跳需要考虑一条重链的一个区间的所有点和它们的所有轻儿子,这是两个标号区间。注意如果信息不幂等,需要换一种对链头的特殊处理(实际上就是不把它算到这条重链里,除了在lca处特判),因为它会作为它父亲的一个轻儿子。

  • 对于子树,考虑这个点所在的重链从它开始往下的部分。它的子树分为这半条重链,这半条重链上每个点的轻儿子,这半条重链上每个点的轻子树,而三部分分别是一个标号区间。

很难写,但是它确实可行。我觉得这个东西肯定不是我第一个搞出来的,所以有没有人有一份简洁的实现?

如果你不需要这么一个dfs序,直接剖,然后修改一个作为轻儿子的点的时候改一下它的父亲,改一条链的时候打一个轻儿子的标记就好了。


Prufer序列

$n$个点的有标号无根树和长$n-2$值域在$1,…,n$的序列形成双射。每个点在序列中的出现次数是它的度数$-1$。


Pick定理

顶点都是格点的多边形面积是$S=in+\frac{border}{2}-1$,其中$in$是多边形内部的格点数,$border$是边上的格点数。


三元环计数

无向图三元环计数说的是,我们先给边定向,从度数小的连向度数大的,然后枚举两层出边打标记,再枚举一条出边统计答案。

这个可以推广到四元环,也就是枚举一层出边和一层无向边打标记,再枚举一层出边和一层无向边统计答案。

这样做,每个点的出度不超过根号,于是复杂度就是正确的(实际上反过来连也是正确的,因为入度不超过根号)。同时我们也证明了三元环的个数是$O(m\sqrt{m})$级别,但是四元环可以达到$\Theta(m^2)$,构造方法是一个点连向一堆点,然后一堆点连向另一个点。

具体证明是,考虑到一个点连到的点度数都比它大,于是如果它的出度是$d$,那么它连向的点的度数都至少是$d$,于是这些点的度数和至少是$d^2$。这些点之间最多连$\frac{d(d-1)}{2}$条边,每条在度数中会贡献两次,所以它们连的边至少有$d^2-\frac{d(d-1)}{2}$条,于是$d$不能超过大约$\sqrt{2m}$,否则就会飞。

这个比根号分治常数要小,并且在一些问题上有更好的性质。

比如 :

lxl口中的经典题

给一张图,支持修改一个点权,查询一个点邻点的点权和。

来自vuq的题

给一张图,一条边的边权是端点点权的和,支持修改一个点权,求所有边的边权max。

做法是一样的,套这个trick然后每个点维护入边的贡献,修改的时候爆力改出边,查询的时候爆力加入出边。


diamond计数

diamond指的是一个四元环加上一条弦。

感觉到中间那条弦是特殊的,发现它是两个经过中间那条弦的三元环,于是结束了。


双栈代替队列维护双指针

有些时候我们双指针的时候需要维护一个满足某种性质的极长区间,数据结构问题是支持判断是否能插入,插入到右边,删除左边。

有些时候删除比较困难,但是合并是简单的,于是我们可以用两个栈来维护。具体地,我们用两个栈维护当前的可行区间的左半边和右半边,这样插入就是push到右半边,删除就是撤销左半边。什么时候把左半边弹空了,我们就爆力重构,把当前的合法区间全部塞进左边的栈,把右边的弹空。这样每个元素只会被插入撤销两次,可以看个图 :

img

这个也被用于类似于滑动窗口的优化建图问题,也就是我们左边后缀和优化建图而右边前缀和,爆了就重构。


Stern-Brocot Tree

有理数的二叉搜索树。关于复杂度的性质是$\frac{n}{m}$到$1$的路径上不超过$\log$次转向,这可以用来在有理数上二分,也就是倍增一口气走到哪。怎么倍增?维护左右第一个祖先,容易把往下走写成线性变换。

s-b树的发现本来就是用来二分有理数的,它的独立发现者之一Brocot就是一名钟表匠。比如如果你有两个齿轮在一根轴上,一个接在电机上而另一个接在指针,你希望这两个齿轮可以把电机的转速变成秒针的转速。齿数显然都必须是整数,于是我们需要用有理数来拟合一个实数。并且这个齿数不能过大,也就是说拟合的时候分子分母都不能过大,于是s-b树这种二分有理数的工具就诞生了。在Pell方程普及前,s-b树仅有的板子题就是divcnt1,它是一个$\tilde{O}(\sqrt[3]{n})$求$d$或者说$\sigma_0$的前缀和的算法的一部分。

在s-b树上二分时,我们需要二分连续走左儿子或右儿子的次数,设为$l$。如果直接二分,复杂度将是$\log^2$的,但是如果我们先倍增一下,得到一个长度在$2l$以内的区间,然后二分,走一段的复杂度就是$\log l$的,而接下来相当于给目标的分子分母都除了一个$l$递归下去,所以总复杂度是一个$\log$。例题可以看naipc 18 F. Probe Droids。

s-b树只包括正有理数,如果加入负的,我们得到s-b环(stern-brocot wreath)(从$\frac{0}{1},\frac{1}{0},\frac{0}{-1},\frac{-1}{0},\frac{0}{1}$开始),它表示平面上所有有理方向。

s-b树上两个点lca的意义是,它俩之间分母最小的数。

每一层的分数$\frac{n}{m}$们的$\frac{1}{nm}$之和是$1$。当然第$0$层除外。$n+m$之和是$2\times 3^{d-1}$,其中$d$是层数或者说深度。

s-b树还有奇怪的几何意义,可以搜索 Ford Circle。


三的倍数

如果$k\bmod{d}=1$,那么一个数膜$d$等于它的$k$进制下各位和膜$d$。

这个结论还有更强的形式。比如$\mathrm{ord}_7(10)=6$,所以第$6$位和第$0$位的贡献是一样的,所以我们可以六位一组加起来。

再比如$2\mid 10$,那么我们只需要看最后一位。

所以结论是,如果$k\bmod{d}=0$,那么一个数膜$d$等于它的$k$进制下最后一位膜$d$;否则这个数膜$d$等于它的$k$进制下每$\mathrm{ord}_d(k)$位一组加起来得到的数膜$d$。

还有一个问题,如果$k^i\bmod{d}$都不是$0$但是也都不是$1$怎么办呢?看起来这就是$d\not\mid k,k\not\perp d$的情况,此时我们好像没有什么好的结论了。


loj3401

摘自memset0的blog。

给一个实数序列$a$,每次给一个区间和实数$x$,查询区间$1-\frac{a_i}{x}$的乘积,输出实数,精度1e-6。$n,q\leq 6\times 10^5,1\leq a_i<x\leq 10^9$。

看到这个形式就直接取$\ln$。我们知道$\exp\ln\left(\prod\limits_{i=l}^r\left(1-\frac{a_i}{x}\right)\right)=\exp\left(-\sum\limits_{i=l}^r\sum_{k=1}^\infty\frac{a_i^k}{kx^k}\right)$,但是这个$\infty$需要取到巨大才能保证精度。这是为什么呢?

因为$\ln$在$(0,1)$上变化太大了。同时注意到$\exp$在$(-\infty,0)$上则变化很小,于是考虑一个牛逼想法,如果$\frac{a_i}{x}$比$0.5$要大,我们就爆力去求这个,注意到对于每次爆力求,答案必然减半,于是超过$\log C$次就可以输出$0$,$C$是精度相关的常数1e6。否则我们展开大概$K=20$项,对每一项求一个前缀和,当然根据$\ln$的展开式收敛速度可以对$K$有一个估计。总复杂度是$O(n(K+\log C))$。


ioi2018 排座位

$v-e=1$的技巧大家都知道!

实际上这一类配凑也有很多,排座位 说的是,矩形等价于恰好有四个拐角。维护拐角即可。

但是这个看起来性质还是比$v-e=1$要拉一些,毕竟它不能做数数题/ll

另一个类似的东西是平面图有$v-e+f=c+1$,$c$是连通块数。这个好像是有些用的。


下面是五个网络流trick。


Konig定理

二分图最小点覆盖等于最大匹配。

注意到二分图上的点覆盖等价于割,因为每条边都要有一个端点被割了。所以最小点覆盖等于最小割,最小割等于最大流,最大流就是最大匹配。

但是一般图上的点覆盖不等价于割,割看起来比点覆盖小了不止一点。

除了找到最小割,另一个构造方法是考虑每条边,如果它的两个端点只有一个在最大匹配中,那么就把它加入点覆盖,做完之后把剩下的边随便选一个端点加入点覆盖即可。据说 直接找到最小割 的性质好一些?

最小点覆盖等于最大独立集,这是显然的,并且对一般图也成立。

有些时候我们会用konig定理求最大匹配之类的。比如cf1710 E。


Hall定理

二分图的左部点有完美匹配,当且仅当对于每个左部点的子集$X$,邻接的右部点子集$Y$大小不更小,也就是说$\vert Y\vert-\vert X\vert>0$。进一步地,左部点的最大匹配中,恰好有$-\min(\vert Y\vert-\vert X\vert)$个点没有匹配到右部点。

套路用法是寻找$\min(\vert Y\vert-\vert X\vert)$,然后这里面的$X,Y$往往有性质,比如$X$必然是一个区间之类的。

对于每个点可以匹配多次的情况,把大小换成可以匹配的次数之和就彳亍了。


最大权闭合子图

一个图的某个子图是闭合的,当且仅当这个子图走不到子图外。每个点有可正可负的点权,求最大权闭合子图。

一开始我们选所有正权点,然后用网络流求出变成合法的最小代价。

保留原图中的边,边权置为正无穷。从源往每个正权点连边,从每个负权点往汇连边,边权都是这个点点权的绝对值。答案是正权点点权之和减去最小割。

最小权闭合子图就直接取负。

经典问题是,图,点有可正可负的点权,边有非负边权,求一个点集的导出子图使得点边权值和最大。

这个经典问题可能是最复杂的经典网络流建图之一。这是怎么想到的呢?考虑我们可以在选择一个点的时候就选择它的所有邻边,那么最后子图内部的边会被统计两次,恰好一端在子图内的边会被统计一次,而这一次我们需要减掉。你发现这个构成了我们选的点集和没选的点集之间的割,于是可以考虑跑一个最小割把它割出来。

首先每个点连一个$s$连一个$t$,割$s$表示选,割$t$表示不选。一开始选所有东西,再跑一个最小割减去不选的。如果一个点选了,另一个点没选,那么它们之间的边也需要割。

然后强行构造边权就行了。选一个点需要支付点权两倍的代价(因为最后要除一个$2$),而可以获得邻边边权和的收益,所以如果不选的话,会支付邻边边权和减去两倍点权的代价,目标是最小化这个代价。先加上一个极大值使得这些都非负(加极大值可行,当且仅当加了的这些边中选的数量是确定的),然后跑最小割就行了。

拿这个写了 最大获利,然后调了一年,发现是读入边那里写成了for(int i=1;i<=n;i++)/jy


退流和辅助网络

有源汇最大流算法的作用是,给一个源点一个汇点,从源点尽可能往汇点流。

于是我们可以选择原问题中源汇之外的源汇来跑。经典的应用是,如果你要加一条边,继续跑就行了,但是如果你要删一条边,比如它是$u\rightarrow v$,可以从汇往$v$流,然后从$u$往源流,这样这条边上的流量就都没了,然后把这条边删掉就行了。

上下界网络流的那个trick我们不妨称为辅助网络。辅助网络看起来比这玩意要更广泛,或者说它可能更本质。为了处理删边,我们直接把边删了,此时有两个点流量不平衡,具体一点就是$u$入大于出,$v$出大于入。于是我们构建一个辅助网络,使得辅助网络上$u$出大于入,而$v$入大于出,并且差分别相同,这样两个网络直接拍起来就平衡了。

来整理一下所有的上下界网络流。


最小割和二分图最大匹配的可行边和必经边

摘抄自ix35的blog。可行边指的是选了还有最优解,不可行边指的是选了没有最优解,必经边指的是不选没有最优解,不必经边指的是不选还有最优解。

不进行详细证明。

先讨论最小割。先跑最大流。

  • 一条边$u\rightarrow v$可行当且仅当这条边满流,并且残量网络上不存在$u\rightsquigarrow v$的路径。如果存在$u\rightsquigarrow v$的路径,那么割掉它之后这条路径就是增广路了,于是这条路径应该也满流,但是它没满流。

  • 一条边$u\rightarrow v$必经当且仅当这条边满流,并且残量网络上存在$s\rightsquigarrow u$的路径和$v\rightsquigarrow t$的路径。容易感觉到此时这条边不得不割,并且如果不存在这样的路径的话,这条边就可以不割了,因为说明前面或者后面有一些充满了的边,可以割那些边来代替这一条。

于是做法就是跑一个scc,然后如果$u\rightarrow v$满流,如果$u,v$不在一个scc那么这条边可行,如果$s,u$在一个scc且$v,t$在一个scc那么这条边必经。

看起来我需要熟练一下kosaraju,现在提到scc总是有点怂啊(

然后是二分图匹配。这就是显然的了,存在一条经过这条边的交替路的话,这条边可行且不必经,否则这条边要么不可行要么必经。

为了判定是否存在交替路,我们还是在残量网络上(保留源汇)跑一个scc,然后对于$u\rightarrow v$,如果$u,v$在一个scc,说明存在一个……一个环经过$u\rightarrow v$,画一画你发现环和交替路是对应的,所以它是可行且不必经的,否则它要么必经要么不可行。

还有可行点和必经点。任何有边的点都是可行点,因为总可以找到一条交替路的。一个点是必经点,当且仅当它和$s$不在同一个scc。


quick hull,以及某种奇怪的lambda技巧

我在写啥啊。感觉写的好智障。

quick hull的经典用法是最小乘积生成树。最小乘积生成树说的是每个点有两个权值$a,b$,求$\left\sum a\right\left\sum b\right$最小的生成树。

容易想到把每条边看成一个向量,要求权值和的$xy$最小的生成树,相当于拿$xy=k$去切,答案必然在下凸壳上取到。可以证明下凸壳点数只有$O(m^2)$,所以我们可以考虑求出整个下凸壳。

现在我们就要使用quick hull算法。它说的是,要求左下凸壳,我们找到凸壳最左的点和最下的点,然后连一条线,在这条线下方找一个点使得它到这条线的距离最大,这样这个点必然在凸壳上。然后递归这个点到左边和下边的部分。

然后这个问题性质非常好。我们考虑这个距离就是在这条线段法向量上的投影长度,注意到这个投影长度是线性的,也就是说我们要求一个mst使得边的向量的和的投影最小,这个和的投影等于投影的和,于是我们就把每条边的边权置为投影长度,然后直接跑一个mst即可。复杂度是$O(m^3\log m)$,反正确实表现优秀。

这个东西也可以推广到别的东西上,反正就是根据投影的线性性拆开和的贡献。比如最小乘积最小割。

那么我们来证明一下为什么这个下凸壳点数只有$O(m^2)$。注意到我们实际上是在拿一个直线切这个凸壳,每条边的边权被我们搞成$a+\lambda b$之后跑mst。注意到根据kru的结论,只有两条边边权的大小改变的时候mst才会改变,于是虽然$\lambda$是连续的,但是大小关系改变只会发生$O(m^2)$次,于是只有$O(m^2)$个$\lambda$可以切到不同的点。

所以实际上最小乘积生成树并不需要用什么quick hull,我们直接对于两条边算出它们会在哪个$\lambda$达到临界,然后把所有$\lambda$都跑一遍就行了。这样就不需要每次重新排序,复杂度降低为$O(m^3\alpha(n))$。但是它是紧的而quick hull非常松

于是得到另一个经典trick,如果一个点在凸包上,那么一定存在一种投影让它露出来。感觉三维最小乘积生成树也可以这么做?但是我不是很会(

这个技术看起来比较适用于总点数巨大,但是一维问题容易解决,希望找到多项式复杂度做法的问题。


差分

如果有个问题,比如区间加fib数,位置$i$加上$f_i$,然后单点查询,那么可以做差分$s_i=a_i-a_{i-1}-a_{i-2}$,这样加fib数就变成差分的区间加了。


线性求多项式卷积的一项系数,线性插值一项系数

抱歉,这是不可能的。但是请注意$O(n^2)$插值所有系数是不需要法法塔并且容易实现的,就直接把拉插的式子那个prod里面的东西全乘起来,每次除掉其中一项就行了,而这个除法是容易计算的。

如果你的卷积是两个东西卷起来,那么可以直接卷。如果你想求系数的前缀和,那么可以拿一边卷另一边的前缀和。如果数量更多,不能避免法法塔。

我感觉我们需要知道很多不可做的问题。把一个问题归结为一个更广泛的问题很可能会帮助我们,但是我们需要知道每个广泛问题和它们的每个特殊情况,比如线性插值一项系数是不可能的,但是线性求两个多项式卷积的一项系数是可能的,如果本来问题是第二个,但是我们直接钦点使用点值,那么就把可做的问题变成了不可做的。这也说明在线性复杂度求系数的时候,点值并不能帮我们做什么,因为点值和系数之间的转换是困难的。


微积分相关

如果你不求理解只希望先用着,那么请记住这句话 :

我们有
\(\mathcal{A}=\mathrm{SEQ}(\mathcal{B})\Rightarrow A(z)=\displaystyle\frac{1}{1-B(z)}\) 请注意你可以,或者说应当把$\displaystyle\frac{1}{1 − B(z)}$看成$1+B(z)+B^2(z)+B^3(z)+…$的简写。
但是它在代数运算下的行为和你平常见到的$\displaystyle\frac{1}{1-x}$的确一样,比如说有$\frac{1-B(z)}{1-B(z)}=1$。
不如说,因为它有这些性质所以我们才这么简写
——x义x《组合对象符号化·构造组合类·Sequence构造》

导数写作$y^\prime=\frac{\mathrm{d}y}{\mathrm{d}x}$,是因为$y^\prime\mathrm{d}x=\mathrm{d}y$。(你真的知道微分的定义吗?)

积分写作$\int_a^b f(x)\mathrm{d}x$,而不是$\int_a^b[x] f(x)$之类的,是因为它就是可以和微分$\mathrm{d}x$配合使用(两边加积分号)。

我以前在积分的时候,会在$\mathrm{d}x$前面加一个空格(而写乘法的时候不会),现在看起来它其实不应该加啊。


接上一个

在一类$k$元组计数的问题中,可以用gf来描述拼接。比如经典的长剖题 hotel,可以用一个三次的gf来描述。可以省掉大量的讨论。


归纳构造

对于一些构造题,如果你发现或者猜测了一个结论,它指出什么情况必然有解,那么就可以直接硬做,砍掉随便一段,使得剩下的部分必然有解。只要能把规模缩小就行。


码力

码力一定要够!

今天是2022-02-24,我来一个码神宣言。码力强了可以让你有胆量尝试更多的乱搞,把更多时间花在思考上。所以下个月要开始每天四场cf vp或者两场icpc vp练码力。

虽然算法竞赛的乐趣在于思考,但是为了能够在有限的比赛时间中思考的更爽,还是需要练一练码力。

今天是2022-03-21,我吐了。还是5h场比较爽。


三维都是排列的三维顺序对数

就是三维都是排列,只求全局顺序对数的。

我们把每两维拿出来跑一遍,答案全加起来得到$s$,然后考虑每一对被统计了多少次。如果它是顺序对,统计了三次;如果都不是,统计了一次(因为三维的关系必然有两维相同)。这里没有考虑逆序对,是因为逆序对就是顺序对。

设两者数量分别是$a,b$,那么有$a+b=\frac{n(n-1)}{2}$,$3a+b=s$,于是我们知道$a=\frac{s-\frac{n(n-1)}{2}}{2}$。


$d(n)$有多大?

$O(2^{\frac{(1+o(1))\ln n}{\ln\ln n}})$。离谱。

在1e9以内它接近三次根号,1e18接近四次根号。


有向图dfs树

有向图dfs树有些时候性质看起来并不好。为了获得优秀的性质,一个方法是找到具有特殊性质的点,然后重新跑dfs树。但是这个好像很少会用到,只在特殊构造的题里面吧。


usaco21Feb Ag Just Green Enough

求01矩阵中全0子矩形个数。

单调栈。如果i弹的时候被j挡住了,那么注意到i这一位的答案由j的答案加上上面一块而来,所以依次递推就好了。


翻硬币游戏

说的是一类博弈游戏,在一个01串上进行,每次可以把一个1和右边的若干位反转,没有1就输了,这里选择可能有一些限制。

结论是每个1之间是独立的,因为0相当于两个1,也就是说操作相当于把前面若干位放上一个1。


线性积性函数狄利克雷卷积

爆力卷出素数幂处的值,然后线筛所有的值,复杂度就是线性。也就是$\sum\limits_{p\leq n}\log_p^2 n=O(n)$。


半在线下凸函数(min,+)卷积

一般是一个一维dp是下凸的,并且会从前面转移过来,并且打表发现对于很靠后的项差分仍然很小。

理论上来讲我们应该把差分数组归并起来。


trie上的子树

这个东西常见于一些关于批量统计xor的问题中。

两个经典结论是,一个trie上的子树xor上一个数还是一个trie上的子树,两个trie上的子树的笛卡尔积是重复若干次的一个trie上的子树。这两个都是容易计算的,可以看一下我在 sdfzoj contest2 C. 成了诗人 的提交。

一个牛逼的结论是,任意两个区间的笛卡尔积是$\log$个重复若干次的区间。但是我不是很会算出这些区间,可能还是需要排序之类的。


tutte矩阵

就是对于一条边$i\leftrightarrow j$,给$e_{i,j}$一个随机值,$e_{j,i}$负的这个值,然后膜大素数求矩阵的rank,答案就是最大匹配。


kru

kru的作用是,根据生成森林构成拟阵的性质,把最小生成森林转化成 加入一条边之后是不是还是生成森林。做pjudge R1 B(2021-2022 ICPC North America Championships. Problem I)的时候见识到了。

然后考虑了一下,枚举扫描线方向的具体做法或者说方向就是,考虑某个集合中最小的和最大的元素。至于是什么集合还得靠悟,考虑出啥也得靠悟。


完美匹配和偶环覆盖

两个完美匹配拼起来是一个偶环覆盖。所以在做类似于完美匹配计数的问题的时候,可以平方一下变成偶环覆盖,然后再考虑开根开出啥来。但是实际上开根开出啥来并不好考虑吧?所以可能只是本来就有平方的时候这么考虑是自然的。

好像22年集训队论文提到了这方面的东西,完美匹配可以直接拿Pfaffian算,对于$2n\times 2n$斜对称矩阵$A$,它的定义是

\[\frac{1}{2^nn!}\sum_{p\in S_{2n}}\mathrm{sgn}(p)\prod_{i=1}^na_{p_{2i-1},p_{2i}}\]

进行斜对称的初等变换(同时交换$i,j$行,列,同时把$i$行,列的倍数加到$j$行,列上不改变Pf;同时给$i$行,列乘一个数,Pf也乘上这个数)对它有效,可以高消消成对角线上排列着若干个$2\times 2$块的形式,所以我们不再需要开根了。


\[\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\] \[\mu^2(n)=\sum_{d^2\mid n}\mu(d)\]

洛谷5176 公约数

看到很复杂的gcd的式子的时候,可以讨论一下,尽可能搞出一些二元的gcd。

如果还有lcm,可以把lcm min-max容斥掉。


bzoj3774

最小割很适合表示pair贡献。如果一个点在很多pair中,但是希望关于它的某个贡献只产生一次,可以给它拆点。


欧拉图计数

计算有多少个$n$个点的简单欧拉图。

欧拉图跟xor关系密切。根据线性基的那一套东西,不管前$n-1$个点怎么连边,最后一个点只连向所有奇点,就可以把图搞成欧拉图。所以答案是$2^{\binom{n-1}{2}}$。


最小方差生成树

最小化方差的式子如果不好拆的话,可以放弃一个性质,也就是方差的式子中把平均值看成一个变量$t$,$t$就是平均值的时候这个式子取得最小值,所以可以外层枚举$t$内层求最小值。然后可能可以用quick hull或者kru排序的结论做掉。


对拍

大样例很假的时候,一定要拍。如果大样例不假,但是时间充足,还是要拍。

有一个简单技巧是,如果要看取膜有没有问题,可以define int long long或者__int128跑两遍。

如果你和我一样不是很常用对拍器,那么把正解和爆力写在一个程序里就行了。

如果你想看一个题的$n,m$是不是开错了或者没开够,可以分别测$n,m$和$m,n$,如果相同那么很可能是对的。


可持久化不合并信息,每个点只需要知道父亲的树

比如点分树。

这是不行的。只能可持久化外向树,并且复杂度和度数相关。也许你会喜欢边分治。


莫队获取区间每个数出现次数的集合

一个序列的所有数中,不同的出现次数只有根号种。莫队获取这个集合的方法是,不超过根号的爆力扫桶,超过根号的,在全局也一定超过根号,所以它们不超过根号个,爆力看它们是不是超过了根号。这个东西可以避免链表或者hash table。


若干个数的所有因数的并的整除意义下的最长反链

若干个数的因数的并的性质是,一个数的所有因数也都存在。

结论是,必然存在一个答案,使得选择的每个数的素因数个数(可重)相同。考虑对于一个不这样的答案,我们可以给其中素因数个数偏大的数砍去一些素因数。于是答案就是出现次数最多的素因数个数的出现次数。


判断环上两条线段是否相交

就是对于$[i,j],[k,l]$,如果$i<k<j<l$或者$k<i<l<j$那就相交了这样的。可以使用$i<l\operatorname{and}(i-k)(j-l)>0$。


掷硬币

出现了奇怪的东西(

生活中我们难免要面临一些选择,比如今天晚上吃什么,明天早上吃什么,明天中午吃什么,明天晚上吃什么……这种时候,我们就需要一些随机数生成器来帮助我们,而掷硬币是一个经典并且非常的帅的方法。random.org是另一个方法。

如果你想要把硬币扔的很高很转,然后用手拍住它,那么你可以尝试这么扔 : 把大拇指顶在食指上并向上用力,把硬币放在食指上,然后用大拇指弹硬币,同时让你的手往正上方移动(不需要幅度很大)。


析合树计数

两个排列的所有连续段集合相同,当且仅当它们的析合树相同,这里 相同 区分析点和合点,以及儿子顺序。或者说合法析合树和可能的连续段集合之间是双射。

一个重要结论是,析点的儿子个数$\geq 4$,并且只要儿子个数$\geq 4$,就存在一个排列具有这样的析点。

2018-2019 ACM-ICPC, Asia East Continent Finals B. Mysterious … Host

对于$n=1,…,N$,求长$n$的排列的连续段集合有多少种。

也就是计数长$n$的排列的析合树数量。

考虑根是析点还是合点。如果根是合点,那么我们把根的各儿子拿出来,必然有一种方法把它们排成上升的(或下降的)。

如果根是析点,那么我们还是把根的各儿子拿出来,如果儿子个数$\geq 4$,那么必然有一种方法把它们排成单排列,否则必然没有。

于是我们设$dp(i)$表示长$i$的排列的析合树个数,$f(i,j)$表示把长$i$的序列划分成$j$段的所有方案中 每一段的析合树个数的乘积 之和,可以做到$O(n^3)$,瓶颈是算$f(i,j)$。

注意到$j\geq 4$的时候这些状态的贡献没有什么区别,所以就$O(n^2)$了。


三角剖分上的扫描线

三角剖分指的是一种图,它是一个正$n$边形的顶点和边,和它的一种三角剖分中的边组成的图。

一个牛逼的扫描线方向是,选择一个外面的边,考虑它所在的三角形,它把这个三角剖分分成了两部分。

一个看起来用处没那么大的扫描线方向是,选择一个三角形,它把这个三角剖分分成了三部分。如果选择包含中心的三角形,那么分成的三部分都不超过一半。

sdsc2020(sdptt) D4 C. geometry

求一个三角剖分的生成树个数。

就找到一条边确定的三角形,然后分成两半递归下去。这条原多边形上的边,如果选了它,那么三角形上另外两条边最多选一条,否则另外两条边随意,然后问题变成需要算一条边选或不选的情况下的方案数,以这条边劈开继续递归下去,就可以保证状态数是$O(n)$。


Ore定理

对于无向图,如果对于任意两个不相邻的点,它们的度数和至少是$n$,那么图必然存在哈密顿回路。

构造方法是,先随便排列这些-点,设为序列$u$,然后每次找到第一个$i$使得不存在$u_i\leftrightarrow u_{i+1}$,再找到$j$满足$i+1<j$,且存在$u_i\leftrightarrow u_j,u_{j+1}\leftrightarrow u_{i+1}$,然后翻转$i+1,…,j$。这样必然会增加至少一个正确的间隔。Ore定理断言必然存在这样的$j$。

更强一点,满足ore定理的图必然是两部点数相等的完全二分图,或者pancyclic graph(包含任意长度的环的图)。

关于有向图,Meyniel断言,强连通图,如果对于任意两个不相邻的点,它们的全度数(入度和出度)和至少是$2n-1$,那么必然存在哈密顿路。

Posa定理

对于无向图,把每个点的度数从小到大排序,设为序列$d$,如果对于所有$i<\frac{n}{2}$,都有$d_i>i$,那么图必然存在哈密顿回路。

这个强于ore定理,但是没有找到相应的构造。

Bondy-Chvatal定理

对于无向图,我们不停找到两个度数和至少是$n$的点,在它们之间加一条边。如果最后得到完全图,那么原图必然存在哈密顿回路。

这个同时强于ore定理和posa定理,但是也没有找到相应的构造。


位运算的分配律

摘自wiki。

\[\begin{aligned} x\operatorname{or}(y\operatorname{and}z)&=(x\operatorname{or}y)\operatorname{and}(x\operatorname{or}z)\\ x\operatorname{and}(y\operatorname{or}z)&=(x\operatorname{and}y)\operatorname{or}(x\operatorname{and}z)\\ x\operatorname{and}(y\operatorname{xor}z)&=(x\operatorname{xor}y)\operatorname{and}(x\operatorname{xor}z) \end{aligned}\]

也就是or和and互相都有分配律,and对xor有分配律。但是or对xor没有。

如果想要记住这个结论,and是乘法,xor是加法。


fuck myself

交换并且足够局部的操作,直接状压dp!

对于任何操作,最优秀的性质就是交换和局部。


分母是任意多项式的整除分块,上取整的整除分块

分母是任意多项式比较简单,就直接考虑下一次变化在哪,然后算出来这个多项式在哪会越过这次变化即可。

上取整的整除分块的结论是,$\displaystyle r=\lfloor\frac{n-1}{\lceil\frac{n}{l}\rceil-1}\rfloor$,注意$n=1$的时候需要特判。


最小线段覆盖 任务调度(线段最大独立集)

大概就是序列上有一些线段(或者说区间),然后求

  • 最小(权)覆盖 : 用最少(权值和最小)的线段覆盖某个给定区间

  • 最大(权)独立集 : 选出最多(权值和最大)的不交线段

。这两个是经典的最短路建图。

如果是区间查询,可以规约dag最短路,难以比$n^2$低poly。(诶后者是不是可以啊?)但是这个问题有很多弱化版是可做的。

CF1684D Serious Business

求一个区间,使得 左右端点的某种权值的和减去区间的最小权覆盖 最大。

dp,设$dp(i)$表示最右边的线段是$i$的答案,那么右端点在这条线段的范围内,而前面的部分需要和前面的状态接起来,用线段树维护区间max来转移。

对应的问题

求一个区间,使得 左右端点的某种权值的和加上区间的最大权独立集 最大。

dp,设$dp(i)$表示最右边的线段是$i$的答案,那么右端点在这条线段的右边,而前面的部分需要从前面的状态转移过来,可以直接维护前缀max。


裴蜀定理的推论

现在有两个长$m$的序列$a_i$和$b_i$,对于足够大的$\gcd(a_1,…,a_m)\mid c$,必然存在一组$x_1\geq b_1,x_2\geq b_2,…,x_m\geq b_m$满足$a_1x_1+…+a_mx_m=c$。

设$s=\sum a_i$,那么对于每个$c\bmod{s}$的值,我们不停给解$x_i:=x_i+1$就行了。

这一trick有可能可以帮你想到同余最短路。


找到出现次数$\geq$一半的数

配对可以找到出现次数$>$一半的数。考虑了一下,发现我们在这么写的时候

1
2
3
4
5
6
7
8
9
10
inline int find(int m)
{
    int now=0,c=0;
    for(int i=1;i<=n;i++) 
        if(a[i]==now) c++;
        else
            if(c==0) c=1,now=a[i];
            else c--;
    return c>0?now:-1;
}

如果有一个数占恰好一半,那就需要它和剩下的数完美匹配,所以要么第一个数就是它,要么和第一个数配对的数是它。结束了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline int find(int m)
{
    int now=0,c=0,c1=0,ct=0,t=-1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==now) c++;
        else
            if(c==0) c=1,now=a[i];
            else
            {
                c--;
                if(t==-1) t=a[i];
            }
        c1+=(a[i]==b[1]),ct+=(a[i]==t);
    }
    if(c>0) return now;
    if(c1*2>=n) return a[1];
    if(ct*2>=n) return t;
}

处理一类特殊的有后效性的dp

所有的环都经过一个点的最小化代价的问题,并且转移的代价总是非负的。比如求以最优策略随机游走到目标点的时候,有一个回到起点的操作这样的。

此时我们可以二分这个点的dp值然后计算,根据算出来的这个点的dp值来判定二分的是大了还是小了。


hash

看到相等,立刻考虑hash。


完美hash

简单的期望线性的完美hash构造方法是简单的,也就是先用一个hash table,然后对于每个桶爆力计算它的完美hash函数。因为存在hash table的每个桶的大小的平方期望是$O(1)$,所以复杂度是期望线性。

复杂的期望线性的完美hash的构造方法也有比较简单的。之前写过bdz,它和这个差不多,不过套了一个cuckoo hash之类的。这些算法的优势在于构造出hash函数之后只需要很小的空间来保存它。


集合hash

最直接的做法是排序之后使用序列hash。

一个被认为性质比较好的方法是使用一个整数hash函数比如splitmix,然后把这些都xor起来。但是这个不能用于多重集。

可以计算$\prod(a_ix+b)\bmod{p}$,其中$x,b$是随机选择的数,$p$是随机选择的素数。由于膜$p$下$n$次多项式最多只有$n$个根,所以它的碰撞概率大概是$\frac{n}{p}$。

一个性质看起来很是不好的hash是开一个hash table,把集合插进去,然后对每个桶里面排序之后使用序列hash,然后对桶之间使用序列hash。唯一的优势是,比起直接排序,它的复杂度是线性的。

树hash

一个简单的树hash是,每一层用一个多重集hash,每一层的hash函数不同。


比赛策略

sd省选,爆力打满就进了。A和B差不止一题,但是进和不进只差爆力。

任何比赛,不管有多么接近正解,留1h打爆力。

如果你会不是很好写的$n\sqrt{n}$和很好写的$n\sqrt{n\log n}$,先写后者。


laofu 模拟费用流 的 Problem 2

数轴上有$n$只老鼠和$m$个老鼠洞。第$i$个老鼠或洞的坐标为$x_i$(为了简洁和原ppt不同)。求所有老鼠都进洞的最小总代价(即找到一组老鼠的完美匹配,最小化行走的总距离)。

设$dp(i,j)$表示考虑前$i$个东西,有$j$个老鼠还没匹配,如果是负数表示有$-j$个洞还没匹配。对于$j\geq 0$和$j<0$分开考虑。转移看起来是

  • 如果遇到了一个老鼠,两边分别全局加

  • 如果遇到了一个洞,决策选不选

    • 如果之前剩下了老鼠,那么必然选它,这是显然的

    • 如果之前啥也没有,需要决策一下

    • 如果之前剩下了洞,那么必然选它。考虑对于任何一个策略,$\vert j\vert$看起来是若干段斜率为$1,-1,0$之一的折线。我们以这条折线中在$x$轴上的点作为分隔,把折线分成若干段,那么这个决策方法说的是,我们所做的就是决策每个以洞开始的段何时开始,然后这一段就一直选下去直到回到$x$轴上。为了证明正确性,我们只需要说明每一个以洞开始的段,一旦开始,则在它结束之前,一直选下去是最优的。考虑如果一段之中,我们中间某个洞没有选,那么把选第一个洞换成选中间这个洞必然更优。因为这是同一段,中间不会触碰到$x$轴,这个交换所做的就是把两个洞之间这一段下移了一个单位长度,所以它仍然合法。同时在由洞开始的一段中,洞的贡献是负的坐标,所以把前面换成后面答案会更小。

考虑如何维护这个东西。我们两边需要支持全局加,平移,查询第一个,看起来肯定可以deque,实际上甚至可以栈。


树邻域交

邻域交还是邻域。


求导

当你看到下降幂$n^{\underline{k}}$,想要把它凑出一个封闭形式,可以考虑使用$\frac{\mathrm d z^n}{\mathrm d z}=n^{\underline{k}}z^{n-k}$,然后把求导提到外面之类的,这个算子称为$\mathrm D$。这个例题在 两类欧拉积分 里面讲到了。

当你看到普通幂$n^k$,想要把它凑出一个封闭形式,可以考虑使用$\left(z\frac{\mathrm d}{\mathrm d z}\right)^k z^n=n^kz^n$这样的,这个算子称为$\vartheta$。

当你想要展开$\vartheta^k$的时候,手玩一下可以发现它会变成若干个$z^i\mathrm D^i$这样的东西,并且系数是斯特林数。具体一点

\[\vartheta^n=\sum_{k=0}^n{n\brace k}z^k\mathrm D^k\]

,当用它搞$n^k$时,对应于把$n^k$展开成下降幂,这可以在下面这个题中体现。

试看看! 例题1.7

联合省选2020 组合数问题

给定$n,x$和$m$次多项式$f$,求

\[\sum_{k=0}^n\binom{n}{k}x^kf(k)\]

膜合数的值。$n,x\leq 10^9,m\leq 1000$。

把多项式拆开。

\[\sum_{k=0}^n\binom{n}{k}k^tx^k\]

那么这个式子就是刚才我们说的东西。记$\vartheta=x\frac{\mathrm d}{\mathrm d x}$,使用$\vartheta^t$。

\[\begin{aligned} &\sum_{k=0}^n\binom{n}{k}k^tx^k\\ =&\sum_{k=0}^n\binom{n}{k}\vartheta^t x^k\\ =&\vartheta^t\sum_{k=0}^n\binom{n}{k}x^k\\ =&\sum_{i=0}^t{t\brace i}\sum_{k=0}^n\binom{n}{k}k^{\underline{t}}x^k\\ =&\sum_{i=0}^t{t\brace i}\sum_{k=0}^n\frac{n^{\underline{k}}}{k!}k^{\underline{t}}x^k\\ =&\sum_{i=0}^t{t\brace i}\sum_{k=0}^nn^{\underline{t}}\frac{(n-t)^{\underline{k-t}}}{(k-t)!}x^k\\ =&n^{\underline{t}}\sum_{i=0}^t{t\brace i}\sum_{k=0}^n\binom{n-t}{k-t}x^k\\ =&n^{\underline{t}}x^t\sum_{i=0}^t{t\brace i}\sum_{k=0}^{n-t}\binom{n-t}{k}x^k\\ =&n^{\underline{t}}x^t\sum_{i=0}^t{t\brace i}(1+x)^{n-t}\\ \end{aligned}\]

最后一步是二项式定理。于是就结束了。复杂度$O(m^2)$。


卡空间

如果你需要卡常,在空间上砍掉什么东西往往很有效。


补图生成子图计数

一个经典问题是算原图的$K_4$数量减去补图的$K_4$数量,要$n\sqrt{n}$。直接算看起来很不行。

考虑对补图的$K_4$,也就是原图的$4K_1$进行容斥,也就是算没有任何一条边的四个点的子图个数。枚举$K_4$的每个生成子图(也就是钦点一些边),以某种递推计算它的容斥系数,递推的依据就是某个图的容斥系数之和应该是$0$。这样递推出来的容斥系数

  • $4K_1$ : 容斥系数是$1$。

  • $2K_1+K_2$ : 考虑它里面有一个$4K_1$,所以它的容斥系数应该是$-1$。

  • $K_1+P_3$ : 考虑它里面有一个$4K_1$,两个$2K_1+K_2$,所以它的容斥系数应该是$1$。

  • $K_1+K_3$ : 考虑它里面有一个$4K_1$,三个$2K_1+K_2$,三个$K_1+P_3$,所以它的容斥系数应该是$-1$。

  • ……

算个锤子。反正可以算。


平衡树多树二分

重量平衡的平衡树可以在$O(1)$时间内找到排名在一个长$\alpha n$的区间中的元素,并根据它把平衡树spilt成左右两个。根据这个设计一个类似于严格线性kth的东西,也就是给每个平衡树找一个中位数(但是这里并不能直接找正中间?),然后按这些中位数的中位数进行一次划分。


树卷积

树卷积是对一类和树形背包类似的树形dp进行复杂度分析的技巧。

我所见过的最复杂的树卷积是,二叉树,有一个常数$k$,每个点的状态数是$\min(\mathrm{size}(u),k)$,合并两个点的复杂度是两边状态数的乘积。多叉树每次加入一个儿子的,可以直接多叉转二叉。接下来证明这个复杂度是$O(nk)$。

考虑如果$k=n$,那么这个复杂度,就相当于是两边各选一个点的方案数,那么发现相当于任意两个点都在且仅在$\mathrm{lca}$处产生一次代价,所以复杂度就是$O(n^2)$。

现在考虑一般的情况,发现不能直接这么用了。考虑所有子树大小$\leq 2k$的点,它们组成若干子树,每一个大小都不超过$2k$,所以根据上面的分析,这部分总共是$O(nk)$。考虑子树大小$>2k$的点,它必然有一个儿子$>k$,那么相当于另一个儿子子树中每个点花费了$k$的代价,然后这些点就对父亲的状态数没有贡献了,相当于用$O(k)$的代价删了一个点,所以也是$O(nk)$。

有时候我们会把这个结论用在别的地方。可以把它抽象为 :

\[\sum_u\sum_{v\in\mathrm{ch}(u)}\min(\mathrm{size}(u)-\mathrm{size}(v),k)\min(\mathrm{size}(v),k)=O(nk)\]

,比如花老师在vuq提到qoj4815 ptzsc22 D3 F. Flower’s Land。


全幺模矩阵

可以看一看 https://www.kuniga.me/blog/2013/08/13/totally-unimodular-matrix-recognition.html。

看起来阳间的结论是 : 置换/转置不改变全幺模性。费用流是全幺模的。如果一个矩阵只有01,且每行的1是连续的,它是全幺模的。如果一个矩阵的每一列从上往下递增,那么它全幺模当且仅当所有$2\times 2$子矩阵幺模。


希尔排序

每次把元素按照膜某个数的余数分成若干个子序列并使用插排,这些膜数组成一个步长序列。如果从小到大使用$n$以内的3-smooth数,复杂度是$O(n\log^2 n)$。不管使用何种步长序列,复杂度都是$\Omega(n(\log n/\log\log n)^2)$。

存在一个被认为最优的序列 A102549,但是它只有前八项。


停时定理求停时

有一个随机过程,它会进行若干步,然后在一定条件下停止,停止时的步数称为停时。求停时的期望。

停时定理说的是,对于一个状态,定义一个函数,如果每走一步它的期望不变,那么它的期望的序列称为一个鞅。结论是,进行任意步之后,它的期望仍然不变。

所以我们可以构造一个势函数,它每走一步期望减少$1$,那么它加上步数就是一个鞅。如果我们可以算出开始和停止时这一函数的值,那么相减就得到停时。


Induction puzzle, Muddy children puzzle

有若干个人,每个人有一个01,至少有一个1,每个人可以看到别人的,但是不知道自己的。接下来进行若干轮,每一轮大家充分思考,然后如果一个人知道自己是1,则声明。

结论是如果有$k$个1,那么所有持有1的人都在第$k$轮声称自己是1。

我们直接证明如下结论 :

结论 有若干个人排成一排,每个人有一个数,每个人可以看到别人的,但是不知道自己的。有若干个不可能出现的序列,实际情况不会包含在其中,并且大家都知道这些序列。接下来进行若干轮,每一轮大家充分思考,然后如果一个人知道自己不可能持有某个数,则声明。那么定义两个序列的距离是不同位置的个数,则第一次有人声明的轮数是 所有不可能序列到实际序列的最小距离。

证明 归纳。我们假设如果第$k$轮第一次有人声明,那么最小距离恰好是$k$。

考虑如果最小距离是$k$,那么根据归纳假设前$k-1$轮没有人声明,此时每个人都知道最小距离至少是$k$。由于每个人都只不知道自己,每个人看到的部分的最小距离要么至少是$k$要么是$k-1$,那么看到$k-1$的人就知道实际上最小距离应该是$k$,于是他会声明。如果没有人看到$k-1$,则没有人声明。

本质上来说,大家是在比较看到的最小距离,但是由于不知道别人比自己大还是小,也不能乱跳,所以只能从$1$开始往上数。

我之前觉得了一下如果你看到的最小距离是$k$,那么答案必然是$k$或$k+1$,所以大家可以直接从$k$开始试啊?但是你和别人看到的不一样,又没法交流,所以如果大家进度不同就假了。

另外,如果所有人看到的最小距离都一样,也就是这个最小距离是$n$,那么就不会有人敢于声明。


类欧几里得算法

有关一条直线下方的格点信息的问题。一般可以抽象成,有一条从坐标轴射向第一象限的射线,考虑其经过的格线,经过一条横线记一个$U$,竖线记一个$R$(如果经过格点则记$UR$;坐标轴不算),这样得到一个序列,然后$U,R$分别代入一个结合律的元素来求值,比如矩阵之类的。

1
2
3
4
5
6
7
8
9
M _calc(long long p,long long q,long long r,long long n,M U,M R)
{
    if(!l) return M();
    if(p>=q) return _calc(p%q,q,r,n,U,pow(U,p/q)*R);
    long long m=((__int128)p*n+r)/q-1;
    if(m==-1) return pow(R,n);
    return pow(R,(q-r-1)/p)*U*_calc(q,p,(q-r-1)%p,m,R,U)*pow(R,n-((__int128)q*m+r)/p);
}
M calc(long long p,long long q,long long r,long long n,M U,M R){ return pow(U,r/q)*_calc(p,q,r%q,n,U,R); }

以上代码求解$\sum\limits_{i=1}^n\left\lfloor\frac{pi+r}{q}\right\rfloor$之类的东西。

大概地说,假设$p\geq q$,我们知道每个$R$前面都有$\lfloor\frac{p}{q}\rfloor$个$U$,于是我们可以$R:=U^{\lfloor\frac{p}{q}\rfloor}R,p:=p\bmod{q}$。否则我们把xy反转,这样横线和竖线反转,$U$和$R$反转,$p$和$q$也反转,此时$p>q$了,就可以继续递归了。


最小表示,最小后缀

考虑我们从左往右枚举一个位置$i$,然后维护之前找到的最小的$j$,然后爆力比较它俩。如果在第$k$次不同了,那么

  • 如果$j$更小,我们知道$1,…,i-1$中$j$是最小的,而$j,j+1,…j+k$分别比$i,i+1,…,i+k$小,所以可以直接$i:=i+k+1$。

  • 如果$i$更小,我们知道$i,i+1,…i+k$分别比$j,j+1,…,j+k$小,所以可以直接$i:=j+k+1$。

每次我们都会让$i+j$变大$k+1$,所以复杂度是线性。


dfa minimization

直接写。已经加入板子库。


变量数量很少的线性规划

对于双变量,这是半平面交。如果不想求出凸包,可以随机增量,依次考虑每个半平面,如果当前答案不满足新的半平面,新的答案必然在上面,于是转化成这个半平面上的一维问题。由于每一步增加最多一个交点,一共出现过$n$个,所以复杂度正确的。

三变量好像也可以这么做,但是投影到任意平面算起来比较麻烦,简单做法是直接三分一维。


排列的奇偶性


钦点退位

数位dp的时候可能需要钦点退位。此时一个阳间的写法是,退位正确当且仅当每一位都在$[0,k)$中($k$当然是进制),并且-1位没有退位。可以看我在xix open cup gp of China K. Three Dimensions的提交。


lovasz local lemma

对于关于一些随机变量的$n$个坏事件,我们希望找到一个随机变量的分配使得每个坏事件都不发生。如果这些坏事件之间比较独立,那么成功的概率是非负的,并且存在一个方法较快地找到它。

具体地,设$\Gamma(A)$是和$A$不独立的事件集合(不包括自己),如果存在一组变量$0<x_A<1$,并且对于每个$A$,有

\[\mathrm{Pr}(A)\leq x_A\prod_{B\in\Gamma(A)}(1-x_B)\]

那么存在一个随机算法,在期望$\displaystyle O\left(\sum_A\frac{x_A}{1-x_A}\right)$轮后给出解,每一轮它重新分配若干个变量。

算法就是直接每次找到一个发生了的坏事件,重新随机所有和它有关的变量。

一个较弱但是可能更容易使用的版本是,如果每个坏事件最多和$d$个其它坏事件不独立,发生概率不超过$p$,并且$p(d+1)\leq \frac{1}{e}$,那么这个东西需要进行期望$\frac{1}{d}$轮。

一个更快的算法是,如果对于一个常数$0<\epsilon<1$,满足

\[\mathrm{Pr}(A)\leq (1-\epsilon)x_A\prod_{B\in\Gamma(A)}(1-x_B)\]

那么我们每次找到一个极大的相互独立的集合,并重新分配其中所有变量,期望轮数是$\displaystyle O\left(\frac{1}{\epsilon}\log\sum_A\frac{x_A}{1-x_A}\right)$。


entropy compress

感觉这东西……不是很懂在说什么。大概是把一类组合对象用一个随机算法和它使用的一个随机数序列进行编码之类的。


block design,有限射影平面

定义一个射影平面是点的集合和线的集合的二元组,其中每条线是一个点的子集,满足

  • 两个点确定一条线。

  • 两条线有恰好一个交点。

  • 存在四个点,使得没有一条线经过其中至少三个。这个条件用来排除一些平凡(但是也许离奇)的情况,比如所有点都在一条线上。

注意到前两个条件对点和线是对称的,所以我们定义一个射影平面的对偶是另一个射影平面,它交换线和点的地位,对偶平面中的一条线上点的集合对应于原平面中一个点所在的线的集合。

一个射影平面上,每条线上的点数相同,当然每个点所在的线数也相同,这个数量$-1$称为射影平面的阶。目前发现的所有射影平面的阶都是素数幂。

构造一类重要的有限射影平面,对于一个有限域$\mathbb{F}_{q}$,考虑其上的三维向量空间。所有一维子空间是点,二维子空间是线,那么这是一个射影平面。为了证明这一点,这里是域所以可以做除法,那么两点线和交点都可以解出来。接下来我们直接用$(a,b,c)$表示一条线,它指的是$ax+by+cz=0$,因为我们压缩了一维子空间。从这里可以看到点和线的对偶性。仿射平面早该图图了。

这个射影平面有$q^2+q+1$个点,因为一共有$q^3-1$个非零向量,而每个一维子空间有$q-1$个点。同时也有$q^2+q+1$条线。每条线经过$q+1$个点,每个点位于$q+1$条线上。

一个经典应用是构造边数在$\Theta(n^{\frac{3}{2}})$,允许有自环的$K_{2,2}$ free graph,或者说构造$1$数量在$\Theta(n^{\frac{3}{2}})$的$n\times n\ 01$矩阵,要求没有一个$2\times 2$的子矩形全是$1$。$K_{2,2}$ free,放缩成任意两个点的邻接点交不超过$1$,那么我们选择一个有限域上的射影平面,选择一个点和边的双射,然后对于每个点,直接以对应的线上的点作为它的邻接点。这个题出现在ptzsc16 D9,fjoi2022,以及arc140e。

一个$t$-balanced incomplete block design指的是有一个集合$S$和一个$t$,选择一个$k<t$,然后选择$S$的一些大小为$k$的子集使得$S$的每个大小为$t$的子集在你选的这些集合中出现次数相等。称为balanced是因为大小都相等,称为incomplete是因为$k<t$。如果选的集合个数和$S$的大小相等,那么它是一个对称bibd,或sbibd。每个有限射影平面给出了一个$2$-sbibd,因为任意两个点确定一条线。除此之外目前只发现了有限个$2$-sbibd。


每次交换任意两个元素,使得两个序列相同的最小交换次数

这个是npc的。


积木大赛

最经典的想法是,考虑如果已经把前$i$个推平了,那么必然有$a_i$次对第$i$个的操作,所以如果$a_{i+1}\leq a_i$,直接把其中若干次向后延申一步即可,否则前面不可能提供更多的操作了,必须从$i+1$开始进行$a_{i+1}-a_i$次操作。

也可以考虑找到最小值。注意到$\sum a_{i+1}>a_i$是一个下界,因为每个操作最多让它减少$1$,而操作整个序列确实让它减少了$1$。


带权dilworth

带权最长反链,等价于把每个点拆成点权个,内部不连边,然后最长反链。带权最小链划分,看起来应该定义为这个拆点之后的问题。


博弈论基本定理

有两个人在空间中移动一个棋子,它的坐标是两个实空间中的紧致凸集中的点$x,y$,最后得分是$f(x,y)$,A希望得分最大而B希望它最小。一个想法是,A选择一个$x$,使得对方所有$y$的选择中,$f(x,y)$的最小值最大。对称的,B选择一个$y$使得$f(x,y)$的最大值最小。如果$f$连续,固定$y$对$x$是上凸的,固定$x$对$y$是下凸的,那么博弈论基本定理断言$\displaystyle\max_x\min_yf(x,y)=\min_y\max_xf(x,y)$。

一个特例是,有两个人在空间中移动一个棋子,它的坐标是两个实空间中的紧致凸集中的点$x,y$,最后得分是$f(x,y)=\sum\limits_{i,j}a_{i,j}x_iy_j$,A希望得分最大而B希望它最小。一个想法是,A选择一个$x$,使得对方所有$y$的选择中,$f(x,y)$的最小值最大。对称的,B选择一个$y$使得$f(x,y)$的最大值最小。博弈论基本定理断言$\displaystyle\max_x\min_yf(x,y)=\min_y\max_xf(x,y)$。可以用线性规划对偶定理证明它,但是我没太看懂,请见 https://fr.wikipedia.org/wiki/D%C3%A9monstrations_du_th%C3%A9or%C3%A8me_du_minimax 。


之前写了很多数论结论,这里收录一些,删掉另一些。


循环节

一个素数$p$的倒数,在$k$进制下的循环节长度是$\mathrm{ord}_p(k)$。

既约分数$a/b$在$k$进制下是纯循环的,当且仅当$b\perp k$。


狄利克雷定理和Linnik定理

素数膜$n$形成$\varphi(n)$个等价类,其中每个等价类的占比趋于$\frac{1}{\varphi(n)}$,并且每个等价类的倒数和都是发散的。

等差数列$an+b$如果满足$a\perp b$,那么其中第一个素数不超过$cb^L$,其中$c$是常数而$L\leq 5$,并且有猜想$L<2$。


Mertens定理

Mertens定理说的是$\prod\limits_{p\leq n}\left(1-\frac{1}{p}\right)=\frac{e^{-\gamma}}{\ln n}\left(1+O(\frac{1}{\log n})\right)=\Theta(\frac{1}{\log n})$,其中$e^{-\gamma}\approx 0.56$。

这个好像真的有用啊。可以看看2022-10-14 nowcoder的C,使用它推出了 一个数的因数倒数和是$O(\log\log n)$。


素数间隔,勒让德猜想

http://sweet.ua.pt/tos/gaps.html

可以看到,1e18以内最大的素数间隔是1e3级别。据猜测\(n\)以内最大素数间隔是\(O(\log^2 n)\)级别。

勒让德猜想断言$[n^2,(n+1)^2]$之间有一个素数。


Mertens猜想

$\mu$的前缀和很小。如果黎曼猜想成立,它将是$O(n^{\frac{1}{2}+\epsilon})$的,并且已经验证它在你会用到的范围内不会超过$\sqrt{n}$。有人猜测它是$O(\sqrt{n})$,有人认为不尽如此,你怎么看?


一些东西的和

在做构造题的时候可能会用到。

费马多边形数定理指出,任意自然数可以表示成不超过$k$个$k$边形数的和,其中三角形数是各$\binom{n+1}{2}$可能比较常用。

希尔伯特-华林定理的一些相关结论指出,任意足够大的自然数可以表示成不超过$k\log k+k\log\log k+Ck$个$k$次方的和,其中$C$是某个常数。一个比较简单的界是$3k\log k+33$。任意自然数可以表示成不超过$2^k+\lfloor\frac{3^k}{2^k}\rfloor-2$个$k$次方的和。

Pollock四面体数猜想指出,任意自然数可以表示成不超过五个四面体数$\binom{n+2}{3}$的和。只用四个,猜想只有有限个反例,它的反例在 http://oeis.org/A000797 ,已知最大的在3e5级别。

Pollock八面体数猜想指出,任意自然数可以表示成不超过七个八面体数$\frac{n(2n^2+1)}{3}$的和。这个好像就被研究的少一点。


Foata变换

一个排列的轮换分解是,选择一个还未处理的$i$,写下$i,p(i),p(p(i)),…$,直到重新遇到$i$,我们得到了一个环。把所有环写在一起就得到整个排列。

一个排列的标准轮换分解是,对每个环,我们选择其中最大的那个$i$作为第一项,然后把所有环按最大值从小到大排序。那么我们知道标准分解和排列是双射,因为从左往右扫,遇到一个前缀最大值,我们就知道出现了一个新的环。一个标准分解,忽略每个数在哪个环之后也是一个排列,所以它是一个排列到排列的双射。从排列到其标准分解的映射称为Foata变换。

如果一个排列有$k$个超越,那么Foata变换之后它有$k-1$个上升。通过下降幂棋盘多项式分解定理,这也给出了欧拉数的一种计算方法。


逆序对数的gf

它是$1(1+z)(1+z+z^2)…(1+z+…+z^{n-1})=n!_z$。


fkt

平面图完美匹配计数。大家都会算pf,但是pf跟完美匹配数差了一个$\mathrm{sgn}$,所以一个想法是通过给每条边加一个$\pm 1$的权把$\mathrm{sgn}$消掉。考虑把$\pm 1$描述成定向,如果有边$i\rightarrow j$,那么邻接矩阵$A$中$A_{i,j}=1,A_{j,i}=-1$。

那么现在我们定义一个排列的贡献是$f(p)=\mathrm{sgn}(p)\prod A_{p_{2i-1},p_{2i}}$。首先我们知道一个匹配对应的所有排列的贡献相等,因为交换两条匹配边的位置,或者交换一条匹配边的端点的位置都不影响$f$。

结论 如果一个平面图满足,对于每个内部面,其边界上恰有奇数条顺时针方向的边,那么每个完美匹配的贡献都是$1$或者都是$-1$。

证明 好像比较复杂,见唐队长的论文 浅谈平面图相关算法。

感觉这个东西的构造一般不会用到吧。


字符串hash

为了构造两个hash值相同的串,考虑实际上这说的是有两个多项式,代入一个数$x$(你的base)求值,那么只有在有限域上它的性质才足够好,而模$2^{64}$不是一个域。为了卡掉它,我们考虑先构造一个在所有点处都是$0$的多项式,注意到如果$x$是偶数,长度超过$64$的串前面都没有贡献,如果$x$是奇数,那么$x$膜各$2^k$都是$1$,于是$\prod(1-x^{2^k})$是一个有效的多项式,它在大约$2^{\sqrt{2\times 64}}$次内就产生了$2^{64}$作为其值的因数。

剩下的问题是如何把这个多项式翻译成串,大力展开它,我们得到thue-morse序列,也就是说只要有$2$的字符集就可以卡自然溢出。

所以为了找到一个简单快速的哈希,考虑取膜数$P=2^{61}-1$,有$x\bmod{P}=x\operatorname{and}P+x\operatorname{shift}-61$。于是做乘法的时候我们拆成低位和高位,直接按这个算即可。


画画在分治法法塔中的应用

比如

\[h_i=\sum_{2j\leq i}f_jg_{i-j}\]

画到平面上,它是一个三角形,然后该怎么分治就非常的直观了。


多叉分治法法塔

$\log/\log\log$叉分治,注意到每一层我们所做的dft总长是$n$。


太阳神的宴会


反射多项式

$F^R=z^nF(\frac{1}{z})$,一般$n=\deg F$。它的经典作用是,考虑$F$的所有根,设为$a_1,…,a_n$,那么$F=\prod\limits_i(z-a_i)$,而$F^R=\prod\limits_i(1-a_iz)$,这个形式在部分分式的时候好像有其作用。


一定程度上使用gf证明lucas,以及关于任意有理分式的类似结论

lucas要求$\binom{n}{k}\bmod{p}$,也就是$[z^k] (1+z)^n\bmod{p}$。

首先一个经典结论是膜素数$p$,有$F^p=F(z^p)$。考虑证明$(F+G)^p=F^p+G^p$,二项式定理展开,我们得到一堆$\binom{p}{i}$,根据kummer定理,其中$p$的幂次,当且仅当$i=p,i=0$两种情况的时候才是$0$。然后我们就知道$\left(\sum\limits_ia_iz^i\right)^p=\sum\limits_i(a_iz^i)^p$,费马小定理一下就好了。显然这玩意对任意元多项式都成立。

此时你可能会想起来为什么我们做$\ln-\exp$多项式快速幂的时候可以膜$p$,因为我们所要的不会被那么大的位置的值影响。

所以继续考虑lucas,我们将$(1+z)^n$分解为$(1+z)^n=(1+z)^{\lfloor\frac{n}{p}\rfloor p}(1+z)^{n\bmod{p}}$,其中$(1+z)^{\lfloor\frac{n}{p}\rfloor p}=(1+z^p)^{\lfloor\frac{n}{p}\rfloor}$,那么提取$z^k$的时候这个卷积必然将$k$也分解为$\lfloor\frac{n}{p}\rfloor p+n\bmod{p}$,然后就得到了lucas定理。

loj6142 加强版

给$n,k$,设$F=((1-z)(1+z))^n$,求$[z^k]F$,膜$998244353$。$n,k\leq 10^{18}$。

还是这么分解,那么问题变成$O(\log_p n)$次求一个,发现它是d-finite的,看起来满足$f_i=f_{i-2}-2\frac{n+1}{i}$,使用$\sqrt{p}\log p$的整式递推即可。

ei指出的问题

求$[z^k]\frac{1}{Q}$。

考虑$Q^p=Q(z^p)$,于是有$\frac{1}{Q}=\frac{Q^{p-1}}{Q(z^p)}$,那么分解$k=pq+r$,答案即为$[z^q]\frac{1}{Q}[z^r]Q^{p-1}$,递归即可。如果$p$很小,$Q$是给定的多项式,设$n=\deg Q$,可以爆力求幂,这个复杂度看起来是$O(p^2+\log_p n)$,或者你可以任意膜数$\ln-\exp$之类的,听起来跑不过$p^2$。如果$p$很大,但是$Q^{p-1}$有些性质,看起来也是可以的。

继续考虑求$[z^k]\frac{1}{Q^m}$,有$\frac{1}{Q^m}=\frac{Q^{pm-m}}{Q^m(z^p)}$。往上乘个$F^t$之类的也是基本一样的。


动态图连通性

对于离线,维护删除时间的最大生成森林。

对于在线,有两个比较厉害的想法。

考虑问题是删边之后拿什么补上。考虑如果一个连通块有恰好一条边连向外面,那么我们维护子树每个点所有邻边编号的xor就可以找到这条边,但是有很多边的时候就困难了。于是我们维护若干层,每条边有$\frac{1}{2}$的概率留到下一层,如果这一层边数$>1$则继续看下一层。那么感觉一下,能找到当且仅当没有一步直接从$2,3,4,…$到$0$了,而这些东西全加起来也只有$\frac{1}{2}$,乘上每个情况出现的概率只会更小,所以有至少$\frac{1}{2}$的概率它是真的(为什么wiki说是$\frac{1}{9}$啊?)。并且测试一下发现它在$0.7$左右。于是多开几个就行了。

另一个想法是爆力去找这条边,考虑在一条边失败了的时候,我们需要一些势能的降低,于是给每条边一个势能,我们希望它很小。经过一些奇怪的想法,初始化每条边的高度是$0$,对每个$k$维护高度$\geq k$的边的高度的某个最大生成森林$T_k$。我们保持$T_k$中每个连通块大小不超过$\frac{n}{2^k}$,于是高度是$O(\log n)$的。删边的时候,从高度$0$开始寻找,在高度$k$,所删的边把$T_k$分成两部分$T_1,T_2$,我们给其中较小的部分,不妨设为$T_1$,找一条高度为$k$的连向$T_2$的边。首先把$T_1$的每条高度为$k$的树边提升$1$,由于它是较小的一边,我们保持了 $T_k$中每个连通块大小不超过$\frac{n}{2^k}$。接下来找到所有高度为$k$的边,如果它不连向$T_2$,则将它的高度提升$1$。当然,提升高度的时候我们尝试在$T_{k+1}$中进行插入。

用$n\lg n$个set维护每个点每条高度的边,开$\lg n$个动态树,它需要支持基本的动态树操作,维护子树大小,找到所有set非空的点。ett/satt这种二叉分治结构看起来还是很好做。第四个对lct来说比较困难,因为一个点需要维护它的虚儿子中子树中有非空set的,不过这并不是完全不可行,先维护一下虚儿子有多少个子树中有非空set,这就可以判断一个点子树中有没有非空set了,然后每个点开一个队列维护所有的可能是虚儿子的点中可能有非空set的就赢了。但是空间是俩$\log$所以常数会很大,还是ett快一些。


用栈排序

有一个排列$a$,把它插入栈,你可以在任意时刻pop,要求pop得到的是$1,…,n$。

贪心地,如果已经pop了前$i$个数,那么当我们遇到$i+1$(要插入或者是栈顶),就一定会pop。有解当且仅当你可以在每一轮pop之后保持栈是递减的,如果它不是那么显然死了,如果它是那么我们总能拿到最小的。

转化一下,如果存在三个位置$i<j<k$,$a_i<a_j$,而$a_k<a_i$,它限制了你到$k$这里才能pop $i$,那么你就不可能保持栈是递减的。如果没有这样的三个位置,那么你总能保持栈是递减的。

xvii poi出现了把数分进两个栈的情况,此时变成,如果存在三个位置$i<j<k$,$a_k<a_i<a_j$,那么$i,j$不能在同一个栈中。