Sengxian's Blog

题目地址

描述

给出一个长度为 $n(n\le 300000)$ 的数列 $A$，问该数列在其所有排列中的，按字典序从小到大排列的排名。输出该排名 $\bmod M(M\le {10}^9)$ 的值。
注意该数列会有重复元素（而相同元素交换位置依然是同一个排列）， $M$ 不保证为质数。

分析

根据字典序的比较过程，如果某个排列 $B$ 小于 $A$，那么一定存在一个最小的 $i$，使得 $B_i < A_i$，我们可以枚举这个 $i\in[0, n - 1)$，这样就可以保证不重不漏。

不妨假设第一位就有 $B_0 < A_0$，那么 $B_0$ 可以选择任何比 $A_0$ 的小的数，剩下 $n - 1$ 个数随便排列，都可以满足条件，可以计算出排列数为（$C_i$ 为数列中第 $i$ 小的数的出现次数，$k$ 表示 $A_0$ 是第 $k$ 小）：

但这样如果有重复元素，是会计算重复的，所以我们必须除掉每种重复元素的排列（$T$ 为种类数）

如果用树状数组维护 $C$，那么 $\sum_{i = 1}^{k - 1}C_i$ 每次可以 $\log n$ 求出，现在问题的关键是 $M$ 不是质数，无法保证分母有逆元，怎么办？

采用BZOJ 2142 - 礼物的做法，分解 ，对于每个 $p_i^{k_i}$ 分别计算答案，再用中国剩余定理合并。
考虑计算答案，对于模 $p_i^{k_i}$，将分子分母表示成 $(a, b) = a\cdot p^b$，这样就能保证 $a$ 的逆元存在，也就能计算答案了，可以考虑写一个结构体来表示，重载一下乘和除，这样比较方便。

注意如果没有比 $A$ 小的排列，$A$ 的排名是 $1$，我傻傻的以为从 $0$ 开始，还以为样例是错的。

复杂度：$O(n\omega(M)\log n)$，其中 $\omega(n)$ 为 $M$ 的不同质因子个数，对于 $M\le {10}^9$，$\omega(M) < 13$。