RainAir
My OI Blog
RainAir
「BZOJ1129」Per

题意:给你一个序列s,你把这个序列的所有不同排列按字典序排列后,求s的排名mod m
不保证 $m$ 是质数。
题解:我们记 $cnt_i$ 表示填到当前 $i$ 这个数还有多少个,不难发现题目要求的是:
$$\sum_{i=1}^n \frac{(n-i)!}{\Pi_j cnt_j} (\sum_{j < s_i}cnt_j)$$

显然后面的和式可以用树状数组轻松维护。
发现 $m$ 不一定是个质数,我们质因数分解后对于每一个 $p_i^{e_i}$ 分开做就好了。中间要将所有的数的 $p_i$ 因子都提取出来。(感觉和礼物那个题差不多)
最后 CRT 合并即可。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/757
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「BZOJ1129」Per
题意:给你一个序列s,你把这个序列的所有不同排列按字典序排列后,求s的排名mod m 不保证 $m$ 是质数。 题解:我们记 $cnt_i$ 表示填到当前 $i$ 这个数还有多少个,不难发现题目要求的是…
扫描二维码继续阅读
2019-08-18
标签
近期评论