题解：P14482 天阶梦游

验题人题解。

首先有一个显然的 $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$ 是一个随机权值排列。

$h3$ 是好计算的，但是你会发现对于每个 $k2$，$w2_{\operatorname{rot}(f_2,k_2,y)}$ 都非常凌乱，不同的 $k2$ 间 $w2_{y}$ 也没什么联系。

但是，我们只需要保证，对于每个 $k2$，$w2_i$ 相同即可，也就是说，对于不同的 $k2$，$w2_i$ 可以不同。

所以我们考虑重新定义 $w3_{k2,i}=w2_{f2(i-k2)}$，注意这里没有了 $+k2$，然后发现就可以使用一维 NTT 计算。

复杂度可以降到 $O(m^2\log m + n)$，但是常数巨大，所以卡不动暴力。

代码可以去看出题人的，我只写了暴力验证数据正确性。