#P1931. [Shoi2007]Permutation 有序的计数

    ID: 953 传统题 1000ms 512MiB 尝试: 130 已通过: 33 难度: 7 上传者: 标签>CF2300提高计数 DPPascal 递推加法原理乘法原理高精度加法高精度减法高精度乘法Day1

[Shoi2007]Permutation 有序的计数

题目描述

矩阵博士近来从事研究排列的工作。他发现,给定一个大小为 nn 的排列,比如我们把它记成 P=(a0,a1,⋯ ,an−1)P=(a_0,a_1,\cdots,a_{n-1})(其中对于每个 ii,规定 0≤ai≤n−10 \le a_i \le n-1)。我们马上就可以统计出 PP 的“有序数”是矩阵博士那些无聊发现中的又一个新名词,博士把它定义成:

$$o(P) = \sum\limits_{i=0}^{n-1} \delta_i, \delta_i = \left\{\begin{matrix} 1\ \ \ a_i=i \\ 0\ \ \ a_i\not=i \end{matrix}\right.$$

为了把有序数研究到底,矩阵博士挑出了所有长度为 nn 的排列中和 PP 有相同有序数的排列,构成一个“有序同类集”,并且仔细地把它们以字典序排成 {P0,P1,⋯ ,Pm}\{P_0,P_1,\cdots,P_m\}。这样,一个排列就可以根据他的有序数和所在的有序同类集中的位置来描述了。注意:由于博士的奇怪天性,有序同类集中的位置总是从 00 开始算起的。 有一天,博士家失火了(这其实是常有的事)。博士的研究手稿里有一些纸张被烧糊了,之后,他急需知道某些排列的有序数和所在的有序同类集中的位置,作为博士的唯一一名助手,你义不容辞地接受了任务。

输入格式

输入的第一行只有一个整数 nn,代表给定排列的长度。输入的第二行开始有 nn 个整数,顺次代表一个排列,注意是排列中的元素是从 00 开始到 n−1n-1 的。

输出格式

只有一行,输出两个整数,第一个整数代表给定排列的有序数,第二个整数代表它所在的有序同类集中的位置。

4
2 0 3 1
0 3

数据规模与约定

对于 40%40\% 的数据,n≤10n \le 10。
对于 100%100\% 的数据,n≤64n \le 64。

题目来源

Day1.