题解：P14482 天阶梦游

not_clever_syl · 2025-11-10 09:31:01 · 题解

验题人题解。

首先有一个显然的 O(m^3n) 暴力做法，期望得分 16。

考虑优化，meet-in-middle 就可以做到 O(m^2n)，期望得分 29。

考虑在去掉 n，我们先预处理每个位置的 k1,k2,k3，与初始 k1,k2,k3 的偏移 d1,d2,d3，然后我们把一个数经历的所有操作写出：

按 | 分割过程后，可以发现首尾两部分都可以变成 s'_i (-k) (f) (+k) a_i。

对于首部，我们可以按 s'_i,a_i 分类，用类似星战中的方式，给每个 i 分配一个权值 w_i，然后枚举 k1 计算：对于一个 k1，做完这个过程后得到 y 的位置的权值和。

尾部可以用 f3 的逆函数做，最后枚举 k2 看哈希值即可 O(m^3+n)，期望得分 66 或更多。

到这里，如果你会写指令集即可直接通过，因为常数本来就挺小的，加上指令集就跑得飞快，甚至跑得比std快。

理论上还有更优的做法，std 使用二维 NTT 优化了计算哈希值过程。

在 O(m^3+n) 做法中，有两个 O(m^3) 的瓶颈，一个在前面 s'_i,a_i 转换到 k1,y 的部分，这个可以通过下标平移转换然后二维 NTT 做。

还有一个是枚举 k2 求答案的时候，这里需要转换一下思路，原来需要枚举 k1,y，然后按 y'=\operatorname{rot}(f_2,k_2,y) 排好序比对哈希值。

我们现在不考虑重排序，而是求 h_{k1}=\sum_{y}w2_{\operatorname{rot}(f_2,k_2,y)}ans_{k1,y}，与 h3=\sum_{y}w2_{y}ans_{k3,y} 比对，w2_i 是一个随机权值排列。