RainAir
My OI Blog
RainAir
「BZOJ2142」 礼物/exLucas

题目链接
题目是让你求一堆 $1e9$ 范围的组合数并且模数不保证是质数。
对于这一类题目,我们有一种叫做 exlucas 的方法来算组合数(但是和 lucas 没有半毛钱关系)。
首先我们将模数 $m$ 质因数分解,最后用 CRT 合并一下就好了。
然后我们现在只需要考虑组合数对 $p^e$ 取模的情况了。
这样还是不能直接去乘逆元的,因为分母可能有因子 $p$,直接求逆元会变成 $0$ 直接自闭。所以我们考虑提取组合数计算公式 $\frac{n!}{m!(n-m)!}$ 中所有的质因子 $p$单独计算。现在我们只需要快速计算出 $a! \mod p^e$ 除掉所有的因子 $p$ 的结果就可以了。
(更广义的说,我们需要计算 $a! \mod p^e$,分开处理 $p$ 和其他数对答案的贡献)
于是我们考虑对于目前处理到 $a! \mod p^e$ 这个问题如何处理:
1. 我们需要找出 $[1,n]$ 中所有是 $p$ 倍数的数,统一提出一个 $p$ ,然后划分为子问题 $(\frac{n}{p})!$ 继续计算
2. 对于非 $p$ 倍数的数,肯定存在连续的 $[1,p^e-1]$ 段,我们只需要统计出一段,然后用快速幂算一下贡献就可以了(因为在模意义下各段答案相同)。
3. 对于一些边角的小东西 暴力算一算就可以了。

时间复杂度由于我 太菜,不会分析。
所以代码大概是这样:

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

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「BZOJ2142」 礼物/exLucas
题目链接 题目是让你求一堆 $1e9$ 范围的组合数并且模数不保证是质数。 对于这一类题目,我们有一种叫做 exlucas 的方法来算组合数(但是和 lucas 没有半毛钱关系)。 首先我们将模数 $m$…
扫描二维码继续阅读
2019-07-21
标签
近期评论