P3477 [POI2008]PER-Permutation

    • 34通过
    • 126提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 POI 2008 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Multiset is a mathematical object similar to a set, but each member of a multiset may have more than one membership.

    Just as with any set, the members of a multiset can be ordered in many ways. We call each such ordering a permutation of the multiset. For example, among the permutations of the multiset{1,1,2,3,3,3,7,8}. there are {2,3,1,3,3,7,1,8} and{8,7,3,3,3,2,1,1}.

    We will say that one permutation of a given multiset is smaller (in lexicographic order) than another permutation, if on the first position that does not match the first permutation has a smaller element than the other one. All permutations of a given multiset can be numbered (starting from one) in an increasing order.

    Task Write a programme that reads the description of a permutation of a multiset and a positive integerm from the standard input, determines the remainder of the rank of that permutation in the lexicographic ordering modulo m, writes out the result to the standard output.

    多重集合是数学中的一个概念,它的定义很像集合,但是在多重集之中,同一个元素可以出现多次。

    和集合一样,多重集的的元素可以有很多种元素的排布顺序。我们把它叫作多重集的排列。

    现在我们定义多重集的某个排列$s_i$比某个排列$s_j$

    的大小比较为字典序比较。这样某个多重集的排列可以从小到大得排起来。

    现在给你一个元素个数为n的多重集的一个排列和m,求这个排列的排名取模m。

    输入输出格式

    输入格式:

    The first line of the standard input holds two integers n($1\le n \le 300000$) and m ($2 \le m \le 10^9$ ) ,separated by a single space. These denote, respectively, the cardinality of the multiset and \dots\ the number m.

    The second line of the standard input contains n positive integers $a_i$($1\le a_i \le 300000$), separated by single spaces and denoting successive elements of the multiset permutation.

    第一行 两个整数n,m

    第二行 n个数,代表多重集的排列

    输出格式:

    The first and only line of the standard output is to hold one integer, the remainder modulo m of the rank of the input permutation in the lexicographic ordering.

    一行一个整数 排名取模m

    输入输出样例

    输入样例#1: 复制
    4 1000
    2 1 10 2
    
    输出样例#1: 复制
    5
    

    说明

    感谢@远航之曲 贡献的翻译

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。