P82908

排列的字典序问题

难度 3 级 初二 分治
讨论 统计 182通过 601提交 30.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

n个元素有n!个不同的排序。将这n!个排列按字典序排列,并编号为0,1,...,n-1。每个排列的编号为其字典序值。

例如,当n=3时,6个不同排列的字典序值如下:

字典序值   0   1   2   3   4   5

排列     123 132 213 231 312 321

输入

输入第一个正整数n。第二行是n个元素{1,2,...,n}的一个排列。

输出

第一行为字典序值。 第二行为按字典序排列的下一个排列。

样例

样例 1
输入
3
1 3 2
输出
1
2 1 3
样例 2
输入
8
2 6 4 5 8 1 7 3
输出
8227
2 6 4 5 8 3 1 7

来源

分治专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交