Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

Solution [USACO20DEC] Spaceship P

posted on 2021-08-19 08:48:46 | under 题解 |

Abstract

昨天有同机房的人说,@GuildingStar 的讲题听不懂,所以我就来写一些粗略的补充。

Solution

首先,我们可以将答案写作从 $s$ 到 $t$ 走 $i$ 步的方案数与上长度为 $i+1$ 的合法按键序列的乘积之和。

并且注意到从 $s$ 到 $t$ 走 $i$ 步的方案数为 ${\mathbf A}^i(s;t)$,其中 $\mathbf{A}^i$ 为邻接矩阵 $\mathbf A$ 的 $i$ 次幂。

所以很容易想到设出一个生成函数 $F(x)$,使得$[x^i]F(x)$ 恰好为长度为 $i$ 的合法按键序列,根据多项式环的通用性质,答案就是 ${\mathbf A^{-1}}F(\mathbf A)$。

进一地,注意到每个合法的按键序列中有唯一的最大值,因为按下最大值之后不可能按到编号更大的按钮,所以我们可以将序列从最大值处断开,分为左右两段独立的区间来处理。

所以我们令 $F_k(x)$ 为所有元素 $\le k$ 的合法序列的生成函数。

写出转移方程$$F_k(x)=x\sum_{i=1}^k(1+F_{i-1}(x))^2$$

解释:枚举序列中的最大值 $i$,拆成左右两段,两段中的元素均 $\le i-1$,然后作个卷积。乘 $x$ 是因为要去掉最大值,$+1$ 是因为我们的生成函数没有常数项,方便之后处理。

我们先预处理出所有的 $F_k(\mathbf A)$,时间复杂度为 $\mathcal O(kn^3)$。

接下来,考虑上序列首、尾的限制,设 $F_{b_s,0,k}(x),F_{0,b_t,k}(x),F_{b_s,b_t,k}(x)$为分别考虑首、尾、首和尾的限制的生成函数,仿照上式写出转移方程$$ \begin{aligned}F_{b_s,0,k}(x)&=x\sum_{i=1}^k\left\{\left[[i=b_s]+F_{b_s,0,i-1}(x)\right]\left[1+F_{i-1}(x)\right]\right\}\\ F_{0,b_t,k}(x)&=x\sum_{i=1}^k\left\{\left[[i=b_t]+F_{0,b_t,i-1}(x)\right]\left[1+F_{i-1}(x)\right]\right\}\\ F_{b_s,b_t,k}(x)&=x\sum_{i=1}^k\left\{\left[[i=b_s]+F_{b_s,0,i-1}(x)\right]\left[[i=b_t]+F_{0,b_t,i-1}(x)\right]\right\} \end{aligned}$$ 设行向量 ${\mathbf \epsilon}_s=([i=s])_{i=1}^n$,实际上,在转移中,我们仅需维护出 $\epsilon_sF_{b_s,0,k}(\mathbf A),F_{0,b_t,k}(\mathbf A)\epsilon_t^{\text{T}},\epsilon_sF_{b_s,b_t,0}(\mathbf A)\epsilon_t^{\text{T}}$ 即可。

总的时间复杂度为 $\mathcal O(kn^3+qkn^2)$。