# 排列的字典序跳转 — 题解

出题人解法：降序后缀与阶乘分块跳跃。Codex（GPT-6）整理循环语义、动态存储、证明与验证，并补充 Lehmer 数字方案。

## 从排列块的末尾跳转

固定前缀后，剩下 $s$ 个不同元素共有 $s!$ 个排列。按首元素从小到大，每一种选择对应一个连续的等大块。

从右向左扫描位置 $i$ ，保持右侧 $s=n-i$ 个数已经降序排列。此时位于当前前缀块的最后一项。设右侧有 $g$ 个数比 $a_i$ 大；它们是降序后缀最前面的 $g$ 项。整个后缀 $[i,n]$ 的最后排列比当前恰晚 $g\cdot s!$ 步。

若剩余步数足够，减去这个数，将 $a_i$ 向右移动到这些较大元素之后，得到更长的降序后缀，继续向左。若 $g=0$ ，不用交换就已经满足不变量。

## 在某个块内部落点

若剩余步数小于 $g\cdot s!$ ，先消耗一步进入下一个首元素块的第一项。然后还可以完整跨过

$$q=\left\lfloor\frac{k-1}{s!}\right\rfloor$$

个块。于是选择右侧第 $q+1$ 小的、更大的数作为新的 $a_i$ .反转降序后缀为升序，与选定元素交换，再把换入的较小元素向左插入正确位置，使余下后缀保持升序。剩余步数变成 $(k-1)\bmod s!$ .

现在是一个按字典序排名还原的子问题。对升序后缀，首元素取第 $\lfloor k/s!\rfloor+1$ 小的数；余数用于下一位。实现以交换和插入维护升序。只有足够小的阶乘对应非零数字。

本题 $12!\le2^{31}-1<13!$ ，因此只存到 $12!$ .右侧超过 12 项时，完整块大于全部剩余步数，商必为零；不用计算大阶乘。降序排列后再走一步回到升序排列。若 $n\le12$ ，先对 $n!$ 取余；否则 $k<n!$ ，最多环绕一次。

## 正确性

降序后缀不变量把当前排列定位在一个块的末尾，计算出的 $g\cdot s!$ 是到扩大后缀末尾的精确距离，完整跳跃不遗漏落点。不能整段跳过时，先跨边界再按整块商选择首元素，余数恰为目标在剩余后缀内的排名；升序还原逐位实现该排名。最终边界的一步环绕也符合题意，故输出正是所需第 $k$ 个后继。

## 复杂度与取舍

设 $K$ 为允许的最大步数，$D$ 为满足 $D!>K$ 的最小正整数；本题 $D=13$ .扫描、至多一次长后缀反转和插入为 $O(n)$ ，短尾的操作总计 $O(D^2)$ .每组时间 $O(n+D^2)$ ，空间 $O(n+D)$ ；最多两次调用不改变此界。所有组的输入输出总量由总长度限制。

默认使用 [std.cpp](std.cpp)。[树状数组补充方案](solution-alternative.zh.md) 更直接地表示排名，但为 $O(n\log n)$ ，本机正式压力超过 0.5 秒时限，作为正确备用方案与交叉验证程序。

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R33.json)