BZOJ 1129 - [POI2008]Per

Published on 2016-09-27

题目地址

描述

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

分析

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

不妨假设第一位就有 B0<A0B_0 < A_0,那么 B0B_0 可以选择任何比 A0A_0 的小的数,剩下 n1n - 1 个数随便排列,都可以满足条件,可以计算出排列数为(CiC_i 为数列中第 ii 小的数的出现次数,kk 表示 A0A_0 是第 kk 小):

(n1)!i=1k1Ci(n - 1)!\sum_{i = 1}^{k - 1}C_i

但这样如果有重复元素,是会计算重复的,所以我们必须除掉每种重复元素的排列(TT 为种类数)

(n1)!i=1k1Cij=1TCj!\frac {(n - 1)!\sum_{i = 1}^{k - 1}C_i}{\prod_{j = 1}^{T}C_j!}

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

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

注意如果没有比 AA 小的排列,AA 的排名是 11,我傻傻的以为从 00 开始,还以为样例是错的。

复杂度:O(nω(M)logn)O(n\omega(M)\log n),其中 ω(n)\omega(n)MM 的不同质因子个数,对于 M109M\le {10}^9ω(M)<13\omega(M) < 13