玄学算法/精彩DS总结 Unqme

## $13.Inclusion-Exclusion\ Principle$ 容斥指的是这样一类问题： 在所有物品中，问在某个条件$C_0$下所有物品的贡献之和。 构造一些**相对容易计算贡献**的条件$C_1,\cdots,C_n$，再对于每个条件构造容斥系数$f_1,\cdots,f_n$，满足对于每个物品 $$\sum_{i=1}^ns(C_i)f_i=s(C_0)$$ ，其中$s(C_i)$表示这个物品在条件$C_i$下所产生的贡献。~~以上全部复读自$\sout{\_\_debug's\ slide}$~~。 ### $13.1$ 组合数容斥 ### $13.2$ 斯特林数容斥 ### $13.3$ 莫比乌斯函数容斥 莫比乌斯反演即为偏序集上的容斥。 实际上，容斥系数关系式满足 $$\sum_{d\vert n}ans_df_\frac nd=realans_n$$ 的时候，$f$就是莫比乌斯函数。 实际上现在推式子题更多地应用到了莫比乌斯函数的性质而不是反演本身。而反演在容斥题中多见。 ### $13.4$ 容斥系数相关 我们怎么理解计算容斥系数的式子呢？ 一般情况下，题目的容斥是以集合大小为容斥系数下标的。那么，容斥系数关系式左边的部分的$s(C_i)$就意味着有多少种方式能够造成这个集合大小，也就是$\binom{n}{i}$。类比这样理解式子，就能很好明白容斥系数的关系式了。 ### $13.4.1$ 如何暴力 首先，如果你知道容斥系数满足的关系式，那你是可以$O(n^2)$进行**递推**的。 对于 $$\sum_{i=1}^ns(C_i)f_i=s(C_0)$$ 来说，其中$s(C_i),s(C_0)$一般都是已经告诉你的，那么你就可以枚举$n$然后根据以前知道的$f$推出现在的$f$。 ### $13.4.2$ 如何优雅 ~~请运用你优秀的大脑，在千变万化中寻找永恒不变的规律，这是真理。~~ 当然一般情况下我们不仅要用到大脑，还要用到**打表**。 ### $13.5$ 最值反演/$\rm min-max$容斥及扩展 这玩意儿指的是 $$\min(S)=\sum_{T\subseteq S}(-1)^{\vert T\vert+1}\max(T)$$ 或 $$\max(S)=\sum_{T\subseteq S}(-1)^{\vert T\vert+1}\min(T)$$ 网上证明有很多，我不会就不写了。 它在期望意义下也成立，因此我们可以很方便地转化一些问题。 但我们可以尝试对它进行扩展。 比如说这样 $$kth\max(S)=\sum_{T\subseteq S}f_{\vert T\vert}\min(T)$$ 我们先来看看这个容斥系数的意义如何。 我们考虑这个集合第$i$大的元素，如果$\min(T)$是这个元素，那么$T$这个集合只可能出现其它$i-1$个比它大的元素，也就是说我们的容斥系数$f$需要满足 $$\sum_{j=0}^{i-1}\binom{i-1}{j}f_{j+1}=[i==k]$$ 这个式子长得非常奇怪，不如设$g_{i-1}=[i==k],f'_j=f_{j+1}$，变成 $$\sum_{j=0}^{i}\binom{i}{j}f'_{j}=g_{i}$$ 那么由二项式反演可得 $$\sum_{j=0}^{i}\binom{i}{j}(-1)^{i-j}g_{j}=f'_{i}$$ $$f'_{i}=\binom{i}{k-1}(-1)^{i-(k-1)}$$ $$f_{i+1}=\binom{i}{k-1}(-1)^{i-(k-1)}$$ $$f_{i}=\binom{i-1}{k-1}(-1)^{i-k}$$ 于是最后就变成了这样 $$kth\max(S)=\sum_{T\subseteq S}\binom{\vert T\vert-1}{k-1}(-1)^{\vert T\vert-k}\min(T)$$ 没有然后了。$kth\min$可以类似求解。 ## $14.Impartial\ Combinatorial\ Game\ Theory$ 博弈论当然就是指博弈啦。这里主要涉及$ICG$博弈。其他部分请移至$Vazuku-46.Asymmertic\ Game\ Theory$。 此段大部分蒯$ATP$博客内容。 ### $14.1\ Sprague-Grundy$ $SG$函数/定理是用来解决对称博弈问题的利器。 $SG$函数的定义是 $$sg(x)=\mathrm{mex}\{sg(nex[x])\}$$ 其中$nex[x]$是$x$的所有后继状态。 然后$SG$定理的定义是 $$all=\sum_{\oplus}sg(G)$$ 其中$G$指的是所有的游戏图。 根据$SG$函数的定义，我们可以发现$sg(x)=0$时其是必败状态，否则是必胜状态。 有了这个东西，我们怎么解决这样的博弈呢？ 首先从题目中发现合理的游戏和游戏的后继状态十分重要。有了这个，我们就可以暴力求$SG$，然后打表找规律。 一般情况下$SG$函数是有规律的，如果没有规律可以根据$SG$函数的值进行一些实现上的优化。比如有整除分块等。 ### $14.2\ Anti-SG$ 自然不可能所有的$ICG$博弈都可以通过$SG$求解。比如如果我们将$Nim$的规则改为无法操作者胜的话情况就不一样了。 但我们有一个名叫$SJ$定理的东西可以解决问题。如果我们仿照之前一样，将$sg(x)=0$视为游戏结束的局面，那么先手必胜当且仅当： $1.sg(S)\neq0$且子树中某个$sg(x)>1$； $2.sg(S)=0$且不存在子树中某个$sg(x)>1$。 然后就可以跟之前一样了。 证明大概可以百度。 ### $14.3\ Staircase\ Nim$ ### $14.4\ Multi-SG\&Every-SG$ $Multi-SG$指的是一个游戏进行操作之后可能会变成多个游戏。 这个的处理非常简单，直接把这多个子游戏的异或和算进去就可以了。显然这些子游戏作为一个整体共同构成了这个后继状态。 $Every-SG$指的是多个游戏同时进行，以最后一个结束的游戏的胜负来判定胜负。 这样的话就在求$sg(x)$的时候加上一个$step$，如果当前是必胜态，那么当前状态的$step=\max\{nex[x]\}$，否则$step=\min\{nex[x]\}$。 这个比较好理解，显然必胜态我们要玩久一点，必败态我们要玩快一点。 ## $15.Gaussian\ Elimination\ in\ DP$ 高斯消元优化$DP$一般应用于求解期望问题时，动态规划转移出现了无序的情况，此时运用递推的形式无法得出每一项的答案，就需要利用高斯消元来解决问题。 首先简单介绍一下高斯消元，大概就是说现在有一个线性方程组变成的矩阵，你把它消成上三角的形式，就可以逐步回代得出每一个未知数的解了。 具体怎么消，就是先枚举每一行，找到当前行对应的数，然后随便在下面找一个这个数的系数有值的行换过来，然后让下面的行的这个数变成$0$，也就是一整行全部减去当前行的某个倍数。 消成上三角后就倒序枚举回代，每次先把当前行减到只有一个元，然后再把元的系数除掉。注意有的题消完之后解是一堆系数用于递推，那么此时这些数也要除元的系数。 一般情况下，我们把期望$DP$的式子要求解的部分就移项到左边，其它部分（常数项和系数）保留在右边就可以了。 ## $15.5.Dynamic\ DP$ 动态$DP$指的是一类问题，这类问题是在$DP$的基础上进行对权值的修改，同时要求用总体较快的复杂度解决。 这里是一个指引。 $Unqme,16.Virtual\ Tree$ $Vazuku,45.Matrix+Size-Subdivision$ ## $16.Virtual\ Tree$ 虚树是一种可以称为数据结构的解题方法。它适用于如下情况的动态DP： ①两点之间的直接信息能够通过$O(1)$或$O(log)$级别等较低级的复杂度得出，或能离线得出； ②保持原树的结构对解题有利； ③缩链不会影响答案的询问； ④询问总点数$\sum k$不多。 若满足①③，我们就可以对每一个询问建立虚树，在虚树上用暴力的DP解决问题。因为一般时间复杂度为$O(queryinfo\times\sum k)$，所以需要满足④我们才能解决问题。 具体来说，虚树的构建方式如下： 首先预处理$dfs$序（包括出栈序$out[u]$），$ST$表。 ①对所有询问点按dfs序排序，然后两两之间求$LCA$。可以证明这样可以求出所有的$LCA$，并与$k$同阶。~~具体的证明可以看zjB博客上那个不清不楚的感性理解法~~本质上是一个维护更优$LCA$集合的过程。 ②重新按$dfs$序排序并去重。 ③用一个栈维护虚树序列，如果$out[stk[tp]]<dfn[fix[i]]$就一直弹掉（当$out[stk[tp]]>=dfn[fix[i]]$时$stk[tp]$是$fix[i]$的祖先~~实际上不可能出现=的情况~~）。 ④此时的$stk[tp]$是$fix[i]$的祖先，直接连边并把$fix[i]$入栈。 ⑤重复这个过程，直到虚树序列被完全遍历。 此时虚树建立完成，可以进行处理。 可以发现，实际上这就是在维护虚树的最右链。 ```cpp sort(fix+1,fix+q+1,cmp); rf(i,q,2)fix[++q]=LCA(fix[i],fix[i-1]);fix[++q]=1; sort(fix+1,fix+q+1,cmp);q=unique(fix+1,fix+q+1)-(fix+1); f(i,1,q) { //printf("%d\n",fix[i]); while(tp&&out[stk[tp]]<dfn[fix[i]])--tp; if(tp)add(stk[tp],fix[i]);stk[++tp]=fix[i]; } ``` （$fix[i]$代表第$i$个询问点~~，为什么叫$\sout{fix}$就不要在意了，~~或许以后会改名吧？）P.S.已经改名为$vir$ ## $17.Segment\ Tree\ Split$ ## $18.Extract\ Key\ Node$ 提取关键点是一种比较冷门一点儿的算法，其特点大概跟点分树差不多，不过是每$\sqrt{n}$深度提取一个关键点。 此坑待填。 ## $19.Matrix\ Multipling$ 发现我矩乘学一次忘一次$\cdots\cdots$ 所以这次记录一下。 对于一个线性递推式/重复且形式相似的递推结构，我们可以对它构造一个01矩阵来进行快速幂优化，复杂度为$O(k^3\log n)$,k为矩阵长/宽。 矩阵乘法的定义大概长这个样子： $$c_{ij}=\sum_{k} a_{ik}b_{kj}$$ 这可以看出它的先决条件是矩阵一的列与矩阵二的行相等。 拿一个转移式子来举例。 **[SHOI2017]组合数游戏** ~~注意此题loj上有部分做法似乎很玄学，正确性存疑。包括我的做法~~ 实质上是求$nk$个里面选若干个使得数量$\%k==r$。 这有一个DP，设$dp[i][j]$表示$i$个里面选若干个使得数量$\%k==j$的方案数。 $$dp[i][j]=dp[i-1][j]+dp[i-1][(j-1+k)\%k]$$ （第$i$个选或不选） 注意$k=1$也没有问题，就是$2^{nk}$。 显然转移是重复了$nk$次的。 于是我们可以列出矩阵： $$\begin{bmatrix}1&1&0&\cdots&0\\0&1&1&\cdots&0\\0&0&1&\cdots&0\\0&0&0&\ddots&0\\1&0&0&\cdots&1\end{bmatrix}\begin{bmatrix}dp[i=0][j=0]\\dp[i][j+1]\\\vdots\\dp[i][k-1]\end{bmatrix}=\begin{bmatrix}dp[i+1][j]\\dp[i+1][j+1]\\\vdots\\dp[i+1][0]\end{bmatrix}$$ 注意初始值是$A[0][0]=1$，但由上可以得出我们第一项其实是$dp[0][1]$，其实没什么关系，转移一次之后，它就变成了$dp[1][1]$，就合法了。 然后可以根据矩乘的定义得知 $$Ans=X^{nk}*A$$ 然后就做完了。注意这题从0开始方便一些。 还有一种线性递推的矩乘操作其实差不多，主要是构造矩阵的时候注意一下就好了。以及是$0\to n-1$还是$1\to n$根据题目判断一下，再就是注意一下矩阵的顺序。 **注意有一种题目是重复转移，比如从$i$转移到$j$，就让$M[j][i]=1$，按照矩阵乘法的定义，这样非常正确。** ## $20.Possibility\&Expectation$ 感觉看了概率期望的slide这么多会做的好少啊......我好菜。 总结一下一些套路： 1. 对于某些方案数相同的不同位置，可以放在一起转移； 2. 树上高斯消元的题目可以大胆设未知数，这个未知数应该也可以推式子解决； 3. 注意有时候某个限制可以转化为一个物品/位置/条件等，然后可以放在一起考虑； 4. 还有很多在我的总结slide里。