2022 软件学院 AK 杯程序设计竞赛

Problem D. 排列的排名

Serein 这天在研究全排列问题，对于 $n$ 个数有 $n!$ 个全排列，但古灵精怪的 Ustinian 问 Serein 能不能对这些排列排个名次。

于是 Serein 定义长为 $n$ 的排列是一个有 $n$ 元素的序列，且 $[1,n]$ 内每个整数出现一次且仅一次，例如 $[1,3,2],[2,1,3]$ 是两个长为 $3$ 的排列。每个排列在所有同长排列里字典序排第几位，就是该排列的排名。例如对于 $n=3$ 时，按字典序列出所有的排列 $[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$ ，则 $[2,3,1]$ 的排名为 $4$ 。

求一个给定排列的排名，可以用康托展开，具体步骤如下：

设初始排名为 $1$ 。
对排列 $p$ 的第 $i$ 个元素 $p_i$ ，找到有多少个整数 $x$ 满足 $x\in[1,p_i]$ ，且 $x$ 未在 $p_1,p_2,\cdots, p_i$ 出现过，设共有 $c_i$ 个数字满足条件，则对排名增加 $c_i\times (n-i)!$ 。

给定一个排列 $p$ ，请你求出它的排名。

输入

输入一行一个整数 $n(1\le n\le12)$ 。

接下来输入一行 $i$ 个整数，第 $i$ 个整数为 $p_i(1\le p_i\le n)$ 。保证 $p$ 是排列。

输出

输出一行一个整数，代表 $p$ 的排名。

样例

标准输入复制文本

5
2 5 3 4 1

标准输出复制文本

标准输入复制文本

5
1 2 3 4 5

标准输出复制文本

标准输入复制文本

3
3 2 1

标准输出复制文本

提示

对于样例1，对 $i=1$ ，只有 $x=1$ 满足，则 $c_1=1$ ，故增加 $1\times 4!$ ；对 $i=2$ ，有 $x=1,3,4$ 满足，则 $c_2=3$ ，故增加 $3\times 3!$ ；对 $i=3$ ，有 $x=1$ 满足，则 $c_3=1$ ，故增加 $1\times2!$ ；对 $i=4$ ，也有 $x=1$ 满足，则 $c_4=1$ ，增加 $1\times 1!$ ；对 $i=5$ ，没有满足的，即 $c_5=0$ ，增加 $0\times0!$ 。故排名为 $1+4!+3\times 3!+2!+1!=46$ 。

登录以提交代码。

单点时限 1 秒

内存限制 128 MB

提交 211

通过 112

A B C D E F G H I J

比赛结束时将在信205 B进行滚榜，有兴趣的同学可以留下来看

注意D题中的！是阶乘的意思

题目难度总体递增但不保证单调递增，被前面题卡住的可以往后面看看

本次ak杯 16：30 封榜，17：10 比赛结束

由于刚开始服务器问题，本次ak杯延长10min，到17:10结束

第一题，只需要输出三次I Miss Serein