一些实用的套路-526互联

计数转期望

有一个形如 \(a_1\ op_1\ a_2\ op_2\ ... op_{n-1}\ a_n\) 的表达式，其中 \(op\) 是运算符，是 \(+,-,\times\) 其中之一。每次操作可以选择一对相邻的数及其中间的运算符进行一次运算，再用答案替换它们三个。问在 \(n-1\) 次操作后，在所有情况下得到的最后的数字的和是多少。
\(1\le n\le 500\)。

首先考虑直接区间 DP，设 \(f_{l,r}\) 为将 \([l,r]\) 内的数全部合并的所有方案的最后的数字和，可以得到一个比较复杂的转移方程：

\[f_{l,r}=\sum_{k=l}^{r-1}{r-l-1\choose k-l}\times \begin{cases}f_{l,k}\times f_{k+1,r}& op_k = \times \\f_{l,k}\times (r-k-1)!+f_{k+1,r}\times (k-l)! & op_k= +\\f_{l,k}\times (r-k-1)!-f_{k+1,r}\times (k-l)! & op_k= -\end{cases} \]

方程的推导比较复杂，需要一定的组合技巧，同时还需要预处理，十分不优雅。

有没有相对简单的方法呢？有。

设 \(E_{l,r}\) 表示将 \([l,r]\) 内的数全部合并，最后合并成的数的期望，那么显然有转移方程：

\[E_{l,r}=\dfrac{1}{r-l}\sum_{k=l}^{r-1} E_{l,k}\ op_k\ E_{k+1,r} \]

最后的答案就是 \(E_{1,n}\times (n-1)!\)。这就比之前的直接计数简单多了，含义也很清晰，从期望的定义就可以直接推出。

换根 DP 推导

换根 DP 的转移方程有没有什么比较套路的方法呢？有。

比如，我们已知在以 \(1\) 为根时的状态转移方程是：

（这是以 \(1\) 为根节点，每次删一个没有父节点的点，求方案数的 DP 方程，推导过程不是此处重点，故略去）

\[f_u=\dfrac{(siz_u-1)!}{\prod\limits_{v\in\text{son}_u}siz_v !}\prod_{v\in \text{son}_u} f_v \]

也已知了以 \(u\) 为根时的答案 \(g_u\)，现在考虑从 \(u\) 转移到 \(x\)，也就是求 \(g_x\)。

首先我们知道：

\[g_u=\dfrac{(n-1)!}{\prod\limits_{v\in\text{son}_u}siz_v !}\prod_{v\in \text{son}_u} f_v \]

（注意，这里的 \(son_u,siz,f_v\) 都是以 \(u\) 为根时的值，但对于 \(x\) 而言， \(siz_x\) 和 \(f_x\) 跟之前的 \(siz_x,f_x\) 是一样的）

我们在 \(g_u\) 中去掉由 \(x\) 及其子树产生的一切贡献，也就是说 \(u\) 的 \(siz\) 会从 \(n\) 变成 \(n-siz_x\)，\(f_x\) 和 \(siz_x\) 产生的贡献也要去掉，设得到的新的 \(g_u\) 为 \(g'_u\)，那么有：

\[g'_u=g_u\times \dfrac{(n-siz_x-1)!}{(n-1)!}\times \dfrac{siz_x!}{f_x} \]

再将 \(u\) 作为一颗子树接到 \(x\) 身上，也就是假设 \(x\) 多了一个子节点 \(u\)，这时 \(f_x\) 将会变成 \(g_x\)，相当于将 \(g'_u\) 作为 \(f\) 与 \(f_x\) 合并，得到 \(g_x\)，表达式是：

\[g_x=f_x\times \dfrac{(n-1)!}{(siz_x-1)!}\times \dfrac{g'_u}{(n-siz_x)!} \]

（注意，这时 \(x\) 的 \(siz\) 发生了变化，从 \(siz_x\) 变成了 \(n\)，需要计算贡献。）

再将 \(g'_u\) 的表达式代入，化简，得到：

\[g_x=f_x\times \dfrac{(n-1)!}{(siz_x-1)!}\times \dfrac{1}{(n-siz_x)!}\times g_u\times \dfrac{(n-siz_x-1)!}{(n-1)!}\times \dfrac{siz_x!}{f_x}=g_u\times \dfrac{siz_x}{n-siz_x} \]

看起来非常简洁，推导过程十分套路，可以套用到大部分换根 DP 的题目。

总结一下，分两步：

在 \(g_u\) 中去掉 \(x\) 的一切贡献得到 \(g'_u\)。
将 \(g'_u\) 的所有贡献全部加入 \(f_x\) 得到 \(g_x\)。

质因子根号分治

在 \(1\sim n\) 中选 \([1,k]\) 个数，使得选出的数的乘积不含平方因子，问方案数。
\(1\le n\le 500\)。

因为 \(\lfloor\sqrt {500}\rfloor = 22\)，也就是说 \(1\sim n\) 中的数最多有 \(1\) 个大于等于 \(23\) 的质因子。

那么我们将 \(1\sim n\) 中的所有数按照其最大质因子分类，最大质因子 \(\in \{2,3,5,7,11,13,17,19\}\) 的单独分一个特殊类，进行状压 DP。

（本身存在平方因子的数直接干掉，不参与分类）

设 \(f_{i,j,state}\) 表示考虑到第 \(i\) 类数，当前选了 \(j\) 个数字，当前小于 \(22\) 的质因子的出现情况是 \(state\) 的方案数。

（\(state<2^8\)，是一个二进制数，也就是状态集合。在一个普通类中只能选一个数，因为选出的数的因子不能重复，重复了乘积就有平方因子了）

那么有状态转移方程：

\[f_{i,j,state}=f_{i-1,j,state}+\sum_{x\in T_i} f_{i-1,j-1,state-st_x}\quad st_x\subset state \]

其中，\(st_x\) 是 \(x\) 的小于 \(22\) 的质因子存在情况，是一个集合，\(T_i\) 是第 \(i\) 类中的数构成的集合。

这是普通类的转移方程，特殊类的也差不多。

时间复杂度比较优秀，属于根号分治的一个特殊应用。

复杂度分析

一个 \(n\times n\) 的方阵，给定所有 \(n^2\) 个点的离开顺序，一个点在离开时如果经过别的点那么代价加 \(1\)，求出所有点离开的最小代价。（一个点离开后之前所在的位置将空开，碰到边界视为离开）
\(1\le n\le 500\)。

暴力是对每个点离开时都跑一遍 01bfs，求出当前其到边界的最短距离，时间复杂度是 \(O(n^4)\) 的。

但是我们发现初始时一个点的离开代价是 \(O(n)\) 的，也就是说，如果我们在一个点离开后以 01bfs 的形式用这个空的位置去更新其他的点的代价，那么时间复杂度均摊为 \(O(n^3)\)，因为一个点每次被更新代价至少减 \(1\)，而代价总和是 \(O(n^3)\) 的，所以更新总次数也是 \(O(n^3)\) 的。（写起来跟暴力差不多）

有一个 \(n\) 点 \(m\) 边的图，在每个点上有一个怪，\(a_i\) 表示杀死这个怪需要已经击杀的怪物数。你需要选择一个 \(a_i=0\) 的点作为起点，判断是否可以杀掉图上所有的怪。在此过程中，你可以通过一条无向边 \((u,v)\) 从点 \(u\) 移动到 \(v\)，前提是 \(v\) 上的怪已经被击杀或者可以被击杀。
\(1\le n,m\le 10^5\)。

（因为题意不太好精简我就把原题面翻译粘过来了）

暴力是对每个为 \(a_i=0\) 的点都跑一遍类 Dijkstra（维护当前 \(a_i\) 的和，从堆中取出 \(a_i\) 最小的并更新其他的点），时间复杂度是 \(O(n^2\log n)\) 的。

事实上，只需要再加一个优化就可以通过本题：如果这个 \(a_i=0\) 的点已经被之前 \(a_i=0\) 的点访问过了那么就跳过。

可以证明，在加了这个优化之后时间复杂度为 \(O(n\log ^2n)\)。

这是因为一个点 \(x\) 能被其他点 \(y\) 访问到的必要条件是 \(siz_y\ge 2siz_x\)，所以一个点最多被访问 \(\log n\) 次，每次是 \(\log n\) 的，所以总时间复杂度为 \(O(n\log^2n)\)。

这里的 \(x,y\) 都是 \(a=0\) 的点，\(siz_x\) 指从 \(x\) 出发最后能击杀的怪物个数，也就是能访问的点的个数。

（点 \(y\) 能访问到 \(x\) 就意味着 \(siz_y-siz_x\ge siz_x\)，也就是 \(siz_y\ge 2siz_x\)）