题解：P13336 [GCJ 2012 Finals] Shifting Paths

· · 题解

写一篇比较新手向的题解供学习。本题参考了 https://www.luogu.com.cn/article/7z4h22vk 和官解，在此致谢。

首先直接考虑的话发现本题并不是一个很传统的问题，因为本题并非最优化或者计数，问题的推进过程是唯一的，如果我们按照要求一直行走，不难想到达到某一长度如果还没有走到 n 就是不合法，否则输出答案。

那么这个的复杂度是多少呢？我们可以试着构造一下。假设对于 i \in [1,n-1]，一条连向 1，一条连向 i+1，那么我们的路径将是类似一个二进制数变化的形式，简单计算可以知道步数是 2^n+2，笔者没有构造出更大的，我们姑且认为该算法复杂度是 O(2^n) 的。模拟可以获得 5 分。

考虑加速。那么我们问题的想法是比较明显的：我们没有办法（或者说不可能）应用一些常用技巧，我们只能试图加速他。一个想法是，我们从构造的解法出发，发现我们重复走了前 \dfrac{n}{2} 非常多变，而如果大约 2^{\frac{n}{2}} 步的缩成 1 步的话那么总复杂就变成 2^{\frac{n}{2}} 左右，就可以接受了。

但我们显然是不可以随便划分的，为了保证复杂度，我们希望没有压缩的部分不会出现重复的状态，这样我们就得到一组解了。考虑如何构造。下面给出官解的构造方式，读者可以先思考再看。

::::info[如何构造] 考虑从 n 点出发沿着反图 dfs（即求出 dfs 树）。然后给每个点标记深度 d_i，并且 d_n=0。然后我们将 d 小的分到 B 部分，其余的分到 A 部分，保证不存在 A 部分是 B 部分的父亲节点。

:::: 通过动态规划，定义 $dp_{i,S}$ 表示从 $i$ 节点进入 $A$，目前 $A$ 集合状态为 $S$（奇数/偶数）最终回到 $B$ 集合时的步数和状态。具体如何转移就是考虑如何移动，移动完到达新节点对应位取反即可。有一个经典的问题是这个会不会出现环以及按什么顺序转移，因为容易发现我们完全有可能从 $S$ 小的转移到 $S$ 大的。 ::::info[解决方法] 我们可以采取记忆化搜索的形式，枚举所有 $S$ 和 $i$，走到相同状态通过记忆化得到答案。容易证明复杂度。 :::: 计算完以后在 $B$ 暴力跳，$A$ 加速即可。下面我们证明不会重复经过一个 $B$ 集合的状态 $S$： ::::info[证明] 考虑反证法。 假设从 $u$ 出发状态为 $S$ 最后回到 $u$，并且 $S$ 不变。考虑开始出发走了一次路径，必定再次回来（$S$ 不变得出的）然后走另一个方向并再次回来结束。那么也就是说，在出现相同 $(u,S)$ 前，一定走过标记为 $d_i-1$ 的节点。考虑标号为 $d_i-1$ 的节点。发现相同 $S$ 意味着相同的状态，那么 $d_i-1$ 与 $d_i$ 同理，那么分析就发现在出现相同状态之前一定会到达 $n$。 证毕。 :::: 第一部分复杂度 $O(2^{|A|}|A|)$，第二部分大概可以估计是 $O(2^{|B|})$，平衡一下复杂度不会超过 $2^{\frac{n}{2}}{n}$。