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

呃。

不知道干什么的时候

(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到右半边，删除就是撤销左半边。什么时候把左半边弹空了，我们就爆力重构，把当前的合法区间全部塞进左边的栈，把右边的弹空。这样每个元素只会被插入撤销两次，可以看个图 :

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

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。

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。

正则图二分完美匹配

正则图二分必有完美匹配。找到一个完美匹配的方法是，随机寻找增广路，复杂度是$O(n\log n)$。

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数就变成差分的区间加了。

接上一个

在一类$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。

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

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

理论上来讲我们应该把差分数组归并起来。实践上确实是这样。

只有一个凸函数的(min,+)卷积

决策单调性分治。也可以smawk，但是谁会写这玩意呢。

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$，它的定义是

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

洛谷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。

也就是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，实际上甚至可以栈。

树邻域交

邻域交还是邻域。

卡空间

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

算原图的$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)$。

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

，比如花老师在vuq提到qoj4815 ptzsc22 D3 F. Flower’s Land。题意大概是，树，对于每个点求包含它的大小为$k$的连通块的最大权值和，n4e4 k3e3 8s。

考虑大力dp，设$dp(u,i)$表示$u$子树选$i$个点的答案，那么为了统计答案我们需要知道上面发生了什么，或者说需要一个换根。注意到上面的dp数组只需要保留$\min(\mathrm{size}(u),k)$项，也就是$>k$和$<k-\mathrm{size}(u)$的都没有用。我们从每个点把这个上面的dp数组传到某个儿子的时候，需要跟别的儿子卷一下，那么为了凑出上面这个复杂度，就需要先求出别的儿子的乘积，然后枚举我们需要的一项和别的儿子的乘积中的一项。直接前后缀积卷起来，一个菊花就卡掉了。考虑我们从左往右枚举一个儿子，把它跟上面的dp数组卷起来，并预处理出后缀积，那么如果现在处理到$v$，枚举后缀积的一项和$v$的需要的一项，设后缀的总点数是$s$，那么前者在$[0,\min(s,k)]$，后者在$[k-\min(k,size(v)),k]$，于是我们用到的前缀积在$[k-\min(k,s+size(v)),k]$之中，这样卷的时候在需要的部分中枚举一个，在正在卷上去的儿子中枚举一个，复杂度就对了。

全幺模矩阵

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

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

Ghouila-Houri判别法 : 全幺模当且仅当对于行的每个子集$r$，都存在一个系数$\pm 1$的线性组合得到一个每一项在$0,\pm 1$中的向量。

希尔排序

每次把元素按照膜某个数的余数分成若干个子序列并使用插排，这些膜数组成一个步长序列。如果从小到大使用$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$开始往上数。

类欧几里得算法

有关一条直线下方的格点信息的问题。一般可以抽象成，有一条从坐标轴射向第一象限的射线，考虑其经过的格线，经过一条横线记一个$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$，所以复杂度是线性。

关于最小表示，更普遍的工具是significant suffix。

dfa minimization

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

变量数量很少的线性规划

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

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

排列的奇偶性

交换任意两个元素，排列的奇偶性反转。注意到每个长$k$的环等价于$k-1$次交换，所以排列和偶环数的奇偶性相同。

排列复合的奇偶性和整数和的奇偶性遵循相同的规律。所以偶排列的复合是封闭的。

钦点退位

数位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$，有

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

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

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

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

那么我们每次找到一个极大的相互独立的集合，并重新分配其中所有变量，期望轮数是$\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。

这里好像有点typo。

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

注意可以有相同的数。这个是npc的。

如果我们可以知道每个数换到哪，答案就是$n$减去环数。

积木大赛

最经典的想法是，考虑如果已经把前$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能移动$x$而B能移动$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)$。

一个特例是，最后得分是$f(x,y)=\sum\limits_{i,j}a_{i,j}x_iy_j$。博弈论基本定理还是断言$\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)$。具体做法大概是它是积性的，对于每个$p^k\parallel n$贡献是$\sum\limits_{i=0}^k\frac{1}{p^k}\leq \frac{1}{1-\frac{1}{p}}$，那么显然这个积在$p$是前若干个素数的时候最大，那么前$\Theta(\log\log n)$个素数的乘积就$>n$了，于是使用mertens定理我们知道它是$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$。于是做乘法的时候我们拆成低位和高位，直接按这个算即可。

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

比如

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

多叉分治法法塔

$\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$不能在同一个栈中。

两条禁止直线的反射容斥

也就是从$(0,0)$出发到$(n,m)$，不碰到$a:x-y=a,b:x-y=b$两条线的路径数。

我们设两条线的距离是$k$，往两边每隔$k$长度再画一条线，现在$x-y=0$上方的线依次记为$a_1,b_2,a_3,b_4,…$，下方是$b_1,a_2,…$，那么一条在原问题中碰到$abab$(连续多次只计一次)的线就对应于新问题中碰到$b_4$的一条线这样的。于是依次减去这些即可。

这样一共只会产生$\Theta(\frac{n+m}{\vert a-b\vert})$条线，所以在预处理之后就是这个复杂度。

矩阵直积(克罗内克积)

https://codeforces.com/blog/entry/96003

向量和向量的笛卡尔积是二维数组。

矩阵描述对向量的线性变换。那么什么描述对二维数组的线性变换?

所以我们就想一个办法，我们把二维数组一列一列串起来变成一个向量，然后用一个矩阵描述对这个向量的线性变换。

如果一个矩阵$A$描述对一个向量的线性变换，它也可以描述对一个二维数组的行们的线性变换，于是它对应于一个对一个二维数组的线性变换$A^\prime$。

现在还有一个矩阵$B$，它可以描述对一个二维数组的列们的线性变换(这个运算也许记为 上乘/kx)，于是它对应于$B^\prime$。我们知道$A^\prime B^\prime$就是这俩的复合。

现在我们换用那个把二维数组拍成向量的表示。此时定义矩阵直积$A\otimes B$是这俩的复合。

一个经典的结论是，$(A\otimes B)(C\otimes D)=AC\otimes BD$。也就是说不同的维度之间是可以随意交换的。

一个经典的用法是，$A\otimes B=(A\otimes I)(I\otimes B)$，同理$A\otimes B\otimes C=(A\otimes I\otimes I)(I\otimes B\otimes I)(I\otimes I\otimes C)$。这个被用来解释法哇塔。

可以看看arc151d。

分散层叠

工业基础。

让我们看看142857cs是怎么说的。

考虑给出一张有向无环图，每个节点的入度和出度都不超过一个常数$d$，每个节点上存有一个有序序列$L_u$。一次查询需要对一个数$q$在一条路径上的所有节点$u$上存有的序列$L_u$中进行二分查找。
对每一个节点$u$建立一个新序列$M_u$，$M_u$由$L_u$和$u$的所有后继$v$上建立的序列$M_v$按一定比例均匀选取元素得到的序列归并得到（如果要做到$O(n)$的空间复杂度，选取的比例必须小于$\frac{1}{d}$），并对每个元素记录下它在$L_u$和每个$M_v$中二分查找的结果。
对于一次查询，我们先在路径的起点$s$上建立的序列$M_s$中进行一次$O(\log n)$的二分查找。假设我们知道$q$在$M_u$中二分查找的结果，要对于$u$的一个后继$v$求出$q$在$M_v$中二分查找的结果。如果我们建立数据结构时选取的比例是$\frac{1}{r}$，那么$q$在$M_u$中二分查找的结果指向的$M_v$中的位置和$q$在$M_v$中二分查找的正确结果的距离不会超过$r$。因为$r$是一个常数，所以可以在$O(1)$的时间复杂度内求出$q$在$M_v$中二分查找的正确结果。
设查询的路径长度为$k$，则单次查询的时间复杂度为$O(k+\log n)$。
——浅谈利用分散层叠算法对经典分块问题的优化 2019锟斤拷锟斤拷息学锟斤拷锟斤拷匹锟斤拷锟叫癸拷锟斤拷锟揭队猴拷选锟斤拷员锟斤拷锟斤拷

试举两例。

排列，对每个$i$求$a_i$在$(i-k,i]$中的前驱，$O(n)$。来自vuq。

按$k$大小分块。如果$i$在$[l,r]$这一块中，那么$[l,i]$中的前驱可以得到区间值域链表后从右往左删除，$(i-k,l)$则不能这么做。考虑把前一块和这一块扔进同一个链表，合并相邻且同属这一块的元素，那么向前找一位就能找到这一块的元素的前驱。在删除一个前一块的元素时可能要合并两个点，好消息是它们是相邻的，按$w$分块，块内压位，块间再用并查集就是线性了，这个称为序列线性并查集。它居然是practical的。

在线区间加区间rank，$O(\sqrt{n})$。

分块，维护每块的有序数组。我们需要在一个区间的所有块上二分，但是如果把块串起来分散层叠，就很难修改了。

考虑在块间建立线段树，支持 从一个点的二分结果得到儿子的二分结果，那么完全覆盖的部分可以打标记，部分重构和没有完全覆盖的部分是两条链，我们两个儿子各取$\frac{1}{3}$合并，则总重构量是$O(\sqrt{n})$的。

只读一遍的根号空间字符串匹配

独立发现了这东西。感觉我很厉害/kx

首先读入$s$，取前$K$个字符，记为$p$，跑kmp的预处理，然后计算后面的hash值。

读入$t$。如果在$(i-K,i]$这里匹配了$p$，那么我们尝试在后面用hash判断。

注意到根据弱周期引理，$p$匹配的位置形成$O(\frac{t}{K})$个等差数列，因为如果相邻三个匹配位置$i,j,k$满足$j-i\neq k-j$，那么必然有$k-i>K$，否则$\gcd(j-i,k-j)$也是周期，$i,j,k$三个位置就不应该相邻了。因此相邻两个匹配位置间的串只有$O(\frac{t}{K})$种，记录它们的长度和hash值即可。平衡一下空间复杂度$O(\sqrt{t})$。

关于简单gf法哇塔的尝试

众所周知or卷积中若干个$(1+az^S)$这样的东西卷起来是可以$O(v\log v)$的。但是xor的好像不是很众所周知。我之前断言它不可做，但是为什么不可做呢?

考虑$1+az^S$的法哇塔是什么样子。$1$的法哇塔是全$1$，而$z^S$的法哇塔是$f_T=(-1)^{\vert T\cap S\vert}$。那么$1+z^S$卷起来实际上是对每个$T$统计有多少个$S$和它的交大小是偶数，如果有$n$个则$f_T=2^n$，如果$<n$那就是$0$，这可以法哇塔一遍得到。然后既然是要做卷积还需要逆法哇塔一下。如果$a$全部相同也可以类似地做。$a=2$见于unr2 黎明前的巧克力。

于是让我们感觉$a$不同的情况不太能做。不如分治法哇塔，那么一个区间的长度不需要开到总和而只需要开到$O(\max)$，于是我们希望排序之后分治，让我们看看这样做的复杂度。有趣的事情是分治的时候每个数平均贡献一次，那么我们希望大的数贡献的尽可能少，于是我们实际上做的事情是排序之后从左往右扫然后卷起来，这需要$\log$次重构法哇塔，但是因为每次倍长，复杂度是$O(v\log v)$，$v$是值域。$1+az^S$是可以$O(v)$算法哇塔的，那么复杂度就是$O(\sum S+v\log v)$，并且这里甚至不需要算法哇塔，直接卷就是$O(\sum S)$的复杂度。如果给的东西项数很多需要$O(v\log v)$跑一个法哇塔，复杂度就是$O(\sum S\log v)$啦。

得到一棵树的所有边，使用$2n+O(1)$个int计算每个点的父亲

拓扑排序。我们对每个点求出度数和所有邻接点的编号的xor，这是$2n$个int。然后找到度数为$1$的点删掉，它的邻接点xor就是它的父亲，更新它父亲的邻接点xor并检查父亲的度数，这个过程只用$O(1)$空间。

这样不一定哪个点作为根。如果要固定根，在扫到它的时候不删它即可。

五子棋

对于任意不考虑禁手的$k$子棋，后手不可能赢，因为如果后手可能赢，先手随便下一步他就变成了后手，而因为先手下这一步只会让他的局势更优，所以他采取后手的必胜策略就赢了。所以问题只是先手必胜还是平局。

一个有意义的转化是，如果后手连$k$个也不算赢，我们得到弱$k$子棋，如果它必然平局，那么$k$子棋也必然平局。

$3\times 3$棋盘上的三子棋，也就是井字棋，是平局的，但是对应的弱问题是先手必胜的。

大家都知道足够大的棋盘上五子棋先手必胜。六子棋看起来未知。七子及以上平局。

对每个数求右边最近的$k$个比它大的数

维护$k$级单调栈，插入一个数的时候用它去弹每一级然后插入第一级，一个数被弹了就进入下一级，那么一个数在第$t$级被弹的时候，正在第一级插入的那个数就是它右边第$t$近的比它大的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
int s[K+1][100002],top[K+1];
inline void clear(){ memset(top,0,sizeof(top)); }
inline void insert(int i,int f[100002][K+1])
{
    for(int k=K;k>=1;k--)
    {
        int last=top[k];
        while(top[k]&&a[i]>a[s[k][top[k]]]) f[s[k][top[k]]][k]=i,top[k]--;
        if(k<K) for(int j=top[k]+1;j<=last;j++) s[k+1][++top[k+1]]=s[k][j];
    }
    s[1][++top[1]]=i;
}

为什么这东西对?我们证明一个数下降当且仅当插入了一个比它大的数，想象一下这$k$级单调栈啥样，它们大概是从上往下依次排列的若干折线，而这个过程大概是画一条横线然后横线下面的shift，于是显然是正确的。

ban线和维护特例

考虑一个经典问题，平面，支持插入删除点，或者给一个点，查询是否有点和它不在同一条横线/竖线/形如$x-y=k$的斜线上。以下把这三种线统称为线。

维护一些特例。有这么几个简单性质 :

• 如果有$3$个点在同一条线上，那么要么它们都被ban，要么至少一个没有被ban。所以一条线上维护超过$3$个点是没有必要的。

• 考虑对于一个查询，它只能ban 大小不超过$9$的已经由上面的条件约简的点集，所以如果我们维护的特例超过$9$个，答案必然是yes。这只是一个简单的判断方法。

需要一个分治结构，复杂度$O(\log n)$。

三角形数点

通过三角形数点也可以边数的线性地做任意多边形数点。

我们数端点之一是原点的三角形。枚举另一点$A$，那么$OAB$中的点就是$O$的极角序区间$AB$和$A$的极角序区间$OB$的卡笛尔积，数点即可。复杂度$O(n^2\log n)$。

简单的建虚树!

勇敢OIer，不怕虚树!

我们按dfn排序，相邻两个点求lca，这就得到虚树上所有点。再按dfn排序并去重，此时为了求出虚树上一个点的父亲，考虑dfn排在它前面的那个点，它要么是这个点的父亲，要么是这个点在父亲其它子树的后代，因此求它俩的lca就得到父亲，每个点往父亲连边就好啦。

耳分解

对于一个强/边双连通图，它的耳是一条链或者一个有端点的环，满足内部每个点度数都是$2$，端点不一定，且删掉内部的点之后剩下的点仍然强/边双连通，可以感觉到这就像一个耳。

耳分解是每次删掉一个耳的分解。

耳分解可以用来生成强/边双连通图，因为加入一个耳显然不影响强/边双连通性。

min-max容斥

关键是min-max容斥应该如何证。它是

一个数产生贡献的$T$，就是比它大的里面任选，小的全都不能选对吧!所以实际上这就是对比它大的数做了一个子集反演。

拓扑序计数

基本不能做。树是可做的，杨表/斜杨表是可做的。

分拆数

它是$\Theta(\frac{1}{n}e^{\pi\sqrt{\frac{2n}{3}}})$的，常数好像很小。

planar separator theorem

把一个平面图可以分成三个点集$A,S,B$，其中$A,B$间没有边，也就是说$A,B$间所有路径都经过$S$，那么$S$称为一个separator。显然bfs树的一层就是一个separator。

planar separator theorem断言任何平面图存在一个separator满足$S$的大小是$O(\sqrt{n})$的，$A,B$大小都不超过$\frac{2}{3}$。那么我们直接套用这个就可以$O(n\sqrt{n})-O(\log n)$求两点间最短路。

根据wiki，我们首先把这个图随便补成一个三角剖分，跑个bfs树。如果bfs树不超过根号层，我们直接从根出发往下选一条路径，满足它尽可能平分两边即可。否则，我们找到上下点数都不超过一半的层，显然这样的层是唯一的，向上向下分别找到第一个点数不超过$\Theta(\sqrt{n})$的层，显然这样的层必然在$O(\sqrt{n})$层内找到。然后在这两层之间找一条路径把中间分成两部分，使得上面拼上中间的一部分和下面拼上中间的另一部分尽可能接近。

例题是ur24 C. 比特之地。注意到我们不一定非要每层都让$A,B$折半，$O(1)$层折半会更好写，如果bfs树超过根号层，看起来直接选一个点数不超过根号且尽可能接近中间的层把它分开就比较对。

随机数据，混乱的pair贡献

随机数据区间最大xor对可以做到$O(n\log n\log v)$。方法是支配对只有期望$O(n\log n)$个，因为固定一个，前缀$\max$个数期望是$\log n$的。可以用可持久化trie找到它们。

对于更一般的问题，可能并不好快速找到这些支配对。

保序回归

保序回归也就是有一个dag，每个点有一个值$y$和系数$c$，给每个点分配一个权值$x$，如果存在$u\rightarrow v$，那么$x_u\leq x_v$，最小化$\sum\limits_u c_u\vert x_u-y_u\vert^k$。当$k\rightarrow\infty$时，最小值不存在但方案仍然存在，此时我们定义问题是把$\sum$换成$\max$。

这玩意性质非常好。整体二分，考虑如果我们限制所有$x$都是$x_0$或$x_0+\epsilon$，计算一个最优解$T$，那么存在一个原问题的最优解满足，$T$中取$x_0$的在原问题中取$\leq x_0$，取$x_0+\epsilon$的在原问题中取$\geq x_0+\epsilon$。这要求$\epsilon$足够小，否则最优解中可能有一个数落在$(x_0,x_0+\epsilon)$。

发现问题是，如果存在$u\rightarrow v$，那么不能出现$u$选$x_0+\epsilon$，$v$选$x_0$。把选$x_0+\epsilon$看成选，$x_0$看成不选，那么就是最小权闭合子图。已经确定的数可以加个虚点。

当$k=1$时，我们知道所有取值都可以是某个$y$，所以只需要在所有$y$上三分，不考虑某个$x$在某个$(y_i,y_{i+1})$中的解。这样就是$\log n$的。

$k>1$时，我没有理解。

这里整体二分可以直接每层跑一遍，看起来会比较好写。但是对于一些奇怪问题可能分开递归会砍$\log$?

$k\rightarorw\infty$时。不需要整体二分，直接二分答案，那么每个数可以取一个区间，沿拓扑序贪心选择最小的合法取值即可。也可以注意到答案就是任意可达点对$u,v$的答案的$\max$，复杂度$O(n^2)$(不考虑算可达性的复杂度)，但是支持加点，在特殊图上可能更有效。

死妈文科smawk

要求完全单调矩阵每行的最小值。

考虑如果我们求出了奇数行的最小值，那么偶数行的直接$O(m)$枚举即可。

问题是递归的时候列数仍然很大，于是复杂度是$O(m\log n)$。考虑我们怎么把列数降下来。

结论是，如果两列$i<j$，在$k$行，$i$比$j$劣，那么$i$只可能包含$<k$的行的最小值，否则，$j$只可能包含$>k$的行的最小值。因为这是一个完全单调矩阵，考虑$2\times 2$的子矩阵即可证明。

考虑对每行维护一个可能的最小值所在列。假设现在已经求出了前$i$行的对应列$p_1,…,p_i$，其中$p_i$在第$i-1$行比$p_{i-1}$劣，那么$p_i$只可能包含$\geq i$的行的最小值。现在要加入新的一列，如果第$i$行对应的列比新一列在第$i$行更劣，那它就不可能包含任何行的最小值了，可以把它扔掉，并继续考虑第$i-1$行。否则，插入新的一列作为$i+1$行的对应列。这就线性了。

中心二项式系数

在看 unr6 神隐，里面用到了$\binom{2n}{n}\sim\frac{4^n}{\sqrt{\pi n}}$。

另外，$\frac{1}{\sqrt{1-4z}}$是中心二项式系数的ogf。

边三

怎么求边三连通分量!

dfs树，每条边分配一个$\mathbf{F}_2$向量，每条非树边分配一维，树边是跨过它的非树边的xor。定义两条边切边等价，当且仅当它们的权值相同。但是这里我们当然不能搞$m-n+1$维向量，所以改成每条非树边分配随机值即可。

可以发现的是，两条边切边等价，当且仅当它们都是割边，或者切断它们断开了一个边双。依此把边双分裂为边三即可。具体地，切边等价的边一定是祖先-后代，因为无向图dfs树没有横向边，我们对于每条边找到最近的和它切边等价的祖先的父边，设这个祖先是$v$，当前边是$u$的父边，那么可以知道$v$的父亲和$u$可能是一个边三，$v$和$u$的父亲可能是一个边三，但是这两组之间必然不是了。再用一组新的随机值确定边三，随机一个数xor到$v$的子树减去$u$的子树，最后新的随机值相等的就是边三连通的。

素域多项式分解

通过不停求导并和自己求$\gcd$可以去除重根。

注意到$z^\frac{p-1}{2}-1$是一个牛逼的多项式，它的根是所有二次剩余，而二次剩余是比较均匀随机的。所以我们随机shift一下和它取$\gcd$，这把它分成两部分，分别递归直到次数足够小即可。

指数提升

现在已经求得多项式方程$f(x)=0$膜$p^k$的所有解$x_0$，要求膜$p^{k+1}$的解。考虑这也就是$f(x_0+p^ky),0\leq y<p$，那么我们把它展开成关于$y$的多项式方程，那么带$y$的只有一次项不会被膜成$0$，解一次方程即可。这个一次方程可能无解，全是解，有恰好一个解，前两种情况比如$f(x)=x^2-a$膜$2$的幂会比较恐怖，它满足$(x_0+2^ky)^2-a=x_0^2-a\pmod{2^{k+1}}$。那么我们怎么办呢，考虑加一次，改为膜$2^{k+2}$，那么如果$k\geq 2$还是会膜没，可以先爆力求出$k=2$的解。现在看起来就是$(x_0+2^ky)^2-a=x_0^2+2^{k+1}y-a\pmod{2^{k+2}}$，这虽然不足以确定$0\leq y<4$，但是足以确定$y\bmod{2}$了，还是每次确定一位即可。

• Previous
  线性规划对偶
• Next
  icpc济南站2021