Solution. Codeforces Round #901

D. Jellyfish and Miku

从 $0$ 到 $n$ 的期望步数可以拆成从 $i$ 到 $i+1$，也即通过每条道路所需的期望步数之和。

我们考虑若相邻两条道路的美丽值分别为 $a,b$，设通过前一条道路期望需要 $x$ 步，通过后一条道路期望需要 $E$ 步，则有方程：
$$
E=1+\frac{a}{a+b}(x+E)
$$
解得 $E=\frac ab (x+1)+1$。

于是，若我们设 $i-1\to i$ 的道路美丽值为 $a_i$，通过 $i-1\to i$ 的的期望步数为 $f_i$，令 $a_0=0,f_0=0$，则有转移 $f_i=\frac{a_{i-1}}{a_i}(f_{i-1}+1)+1$。

为了让转移方程更加简洁，我们现在令 $f_i$ 表示原来的 $f_i+1$，则转移变为 $f_i=\frac{a_{i-1}}{a_i}f_{i-1}+2$。

观察 $\frac{a_{i-1}}{a_i}$ 这个分式，我们发现连续的这种分式乘起来有相当好的性质，于是考虑将转移方程中的 $f$ 不断带入。
$$
\begin{aligned}
f_i&=\frac{a_{i-1}}{a_i}f_{i-1}+2\\
f_i&=\frac{a_{i-1}}{a_i}\left(\frac{a_{i-2}}{a_{i-1}}f_{i-2}+2\right)+2\\
f_i&=\frac{a_{i-2}}{a_i}f_{i-2}+\frac{2a_{i-1}}{a_i}+2\\
f_i&=\frac{a_{i-3}}{a_i}f_{i-3}+\frac{2(a_{i-2}+a_{i-1})}{a_i}+2\\
&\dots
\end{aligned}
$$
直到递归进行到 $f_0$ 时，此时第一项形如 $\frac{a_0}{a_i}f_0$，其值为 $0$，于是 $f_i$ 可以写成更加漂亮的形式：
$$
f_i=\frac{2\sum_{j<i}a_j}{a_i}+2
$$
现在问题转化为最小化 $\sum_i\frac 1{a_i}\sum_{j<i}a_j$。我们设 $dp_{i,j}$ 表示考虑了前 $i$ 条道路，已经分配了 $j$ 的美丽值时前述式子的最小值。有转移：
$$
dp_{i,j}=\min\left\{dp_{i-1,k}+\frac{k}{j-k}\right\}
$$
可以证明，转移时的代价满足四边形不等式，从而这一 dp 有决策单调性。

由于分层转移，我们可以使用分治优化 dp，复杂度为 $O(nm\log m)$；也可以直接运用序列分割 dp 中的结论，也即设 $dp_{i,j}$ 的最优转移点为 $opt_{i,j}$，我们有 $opt_{i,j-1}\le opt_{i,j}\le opt_{i+1,j}$，复杂度为 $O(nm)$。

E. Jellyfish and Hack

首先 $k>n(n+1)/2$ 时必然无解，我们只需考虑剩余情况，此时可以认为 $k$ 与 $n^2$ 同阶。

设 $f_{x,k}$ 表示有多少种 $1\sim x$ 的排列会使得算法运行总步数为 $k$。

枚举排列的第一个数，我们有转移 $f_{x,k}=\sum_i\binom{x-1}{i}\sum_jf_{i,j}f_{x-1-i,k-x-j}$。

不难发现后面那个和式相当于对 $f_i$ 和 $f_{x-1-i}$ 做卷积，但是 $10^9+7$ 的模数使得我们无法使用 NTT。

由于我们最后实际上只需要知道 $f_n$ 的系数，$f_n$ 的度数为 $n(n+1)/2$，于是我们可以做一件类似 NTT 优化 dp 的事情，考虑只记录 $f_i$ 在 $1\sim n(n+1)/2+1$ 上的点值，并直接利用点值转移，最后即可用拉格朗日插值计算 $f_n$ 的系数。

dp 的时间复杂度是 $O(n^4)$，暴力计算多项式乘除法进行拉格朗日插值的时间复杂度为多项式度数的平方，本题中即为 $O(n^4)$。总复杂度 $O(n^4)$。

F. Jellyfish and OEIS

太深刻。

首先，对于总共的 $\sum m_l - l + 1$ 个可能不合法的区间，我们考虑钦定其中一些为不合法，然后利用超集容斥计算答案，此时对于一种钦定方式而言，若钦定了 $c$ 个区间不合法，其容斥系数为 $(-1)^c$。

接下来我们需要计算的就是所有钦定方式下「方案数乘上容斥系数」的和。

如果不合法区间交叉，我们计算方案数是困难的。首先发现，不合法区间交叉的情况下，其带来的约束总是等价于某种不交叉的情况。例如如果有 $a<b<c<d$，限制 $[a,c),[b,d)$ 等价于限制 $[a,b),[b,c),[c,d)$。此外，在限制 $[a,c),[b,d)$ 的时候，是否存在限制 $[a,b)$ 实际上无关紧要。于是在存在区间交叉的情况下，我们可以用如下算法构造双射：先找出字典序最大的交叉区间 $[a,c),[b,d)$，若还存在限制 $[a,b)$ 则将其去掉，否则将其加上。一组映射中的两种钦定方式方案数相等，容斥系数相反，所以会在最终的计算中抵消。所以我们可以只考虑不合法区间不交的情况。

此时所有区间只可能不交或包含，我们可以用区间 dp 来解决这一问题。具体的，设 $f_{l,r}$ 表示只考虑 $[l,r]$，必须钦定 $[l,r]$ 不合法，所有钦定方式下方案数乘上容斥系数的和；设 $g_{l,r,x}$ 表示只考虑 $[l,r]$，有 $x$ 个位置不被限制，所有钦定方式下的方案数乘上容斥系数之和。转移就比较简单了。

总复杂度 $O(n^4)$。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。