排列的字典序跳转¶

背景故事¶

展柜里的一排编号模型每天换成字典序中的下一个排列。最后一个排列之后回到第一个。管理员希望直接算出若干次轮换后的摆放顺序。

(本故事由GPT-6重写)

给定 \(1,\ldots,n\) 的一个排列和非负整数 \(k\) ，将所有 \(n!\) 个排列按字典序从小到大排成一个环，输出向后前进 \(k\) 步的排列。字典序比较在第一个不同位置比较数值。最后的降序排列的下一项是升序排列。\(k=0\) 时保持输入排列。各组数据独立。

第一行组数 \(T\) .每组先读一行 n k ，再读一行包含 \(n\) 个数的排列。

每组输出一行，包含得到的 \(n\) 个数。

1 3 2
1 2 3
1 3 2

2
1 2147483647
1
4 0
2 4 1 3

1
2 4 1 3

1
4 5
2 1 4 3

3 1 2 4

样例 1 展示一步跳转、从降序环绕到升序，以及跳过一个完整周期。样例 2 展示单元素排列和零步。样例 3 从 [2,1,4,3] 前进五步，得到 [3,1,2,4]。

三个元素的六个排列构成一个循环。

\(1\le T\le10^5\) ，每组 \(n\ge1\) ，所有组的 \(n\) 之和不超过 \(2\times10^6\) ；\(0\le k\le2^{31}-1\) .

规格由 Codex（GPT-6）重新设计：明确循环字典序任务、多组格式、总规模和步数范围。

时间 0.5 秒；内存 128 MiB。时限为标准程序每例五次测量的最慢中位数乘以 2，向上取整到 0.5 秒。