锻炼自己的思维链优化能力。
首先比较容易想到设 \(f_{i, j}\) 为从 \(i\) 开始走 \(j\) 步有多少种方案，有一个基于字典序贪心搜索的 \(O(nm)\) 解法。
发现一个事情，\(f_{p_1, m}\) 的大小接近 \(2^m\) 级别，这是一个非常大的数，不难想到，字典序第 \(k\) 小的方案在前面若干步与最小的方案完全一样，根据级别分析，最多在最后 \(64\) 步左右不一样，因此 \(f_{i, j}\) 的 \(j \le 64\)，由于你注意到前面相同步的形式一定形如走若干步在某相邻两个不同的数之间来回跳，最多跳 \(n\) 次就跳到了，因此复杂度为 \(O(n \log m)\)。
不妨大胆一点，为什么我们分析出了 \(2^m\) 这个级别，是因为除了开头结尾每一步都可以选向前还是向后，聪明的你发现，当 \(f_{i, j}\) 的 \(i \in [64, n - 63]\) 时，\(f_{i, j} = 2^j\)，因为其根本不会碰到头，所以此时优化一下复杂度即可变为 \(O(n + \log^2 m)\)。
总而言之，这道题目每一步都不是很难，很好的锻炼了常规思路与处理技巧的运行方式！