P3477 [POI 2008] PER-Permutation

A multiset is like a set, but elements may appear more than once. A permutation of a multiset is any ordering of its elements. 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 use lexicographic order to compare two permutations: at the first position where they differ, the permutation with the smaller element is considered smaller. All permutations of a given multiset can be sorted increasingly and numbered starting from 1 (this number is called the rank). Task: Given a permutation of a multiset of size n and a positive integer m, compute the remainder modulo m of the rank of this permutation in lexicographic order.

- The first line contains two integers n and m ($1 \le n \le 300000$, $2 \le m \le 10^9$): the size of the multiset and the modulus m. - The second line contains n positive integers $a_i$ ($1 \le a_i \le 300000$), the given permutation of the multiset.

Output a single integer: the rank of the given permutation in lexicographic order, taken modulo m.

Thanks to @远航之曲 for the translation. Translated by ChatGPT 5