写了个 TODO List,现在不会忘写博客了
咕
# 题面
> Link DarkBZOJ 2142
$n$ 件不同的礼物送给 $m$ 个人,其中送给第 $i$ 个人礼物数量为 $w_i$。计算出送礼物的方案数(两个方案被认为是不同的,当且仅当存在某个人在这两种方案中收到的礼物不同)。由于方案数可能会很大,输出模 $P$ 后的结果。
设 $P=p_1^{c_1}p_2^{c_2}\cdots p_t^{c_t}$,$p_i$ 为质数,则保证 $p_i^{c_i}\le10^5$。
# 解析
普通的 Lucas 定理只能用来求组合数模较小的素数的问题。
(部分) Lucas 定理
$$ \binom{n}{m}\bmod p=\binom{\lfloor\tfrac{n}{p}\rfloor}{\lfloor\tfrac{m}{p}\rfloor}\binom{n\bmod p}{m\bmod p}\bmod p $$
(但是似乎不是完整的 Lucas 定理?)
而 exLucas 定理可以解决 $p$ 不是一个质数的问题(只要满足「BZOJ 礼物」这道题对 $p$ 的限制即可)。
首先对 $p$ 进行质因数分解 $p=\prod\limits_{i=1}^tp_i^{c_i}$,设 $x=\binom{n}{m}\bmod p$,$x_i=\binom{n}{m}\bmod p_i^{c_i}$,则
模数互质,可以直接CRT。所以问题转化为「组合数模一个质数的幂 $p^k$」。
把组合数的式子展开 $\binom{n}{m}=\frac{n!}{m!(n-m)!}$,我们不能直接求 $m!$ 和 $(n-m)!$ 的逆元,因为它们不一定和 $p$ 互质。于是想到,可以先把阶乘中 $p$ 的因子部分提出来,剩下的与 $p$ 互质的部分就可以求逆元。即
其中 $p\not\mid b$,$(n-m)!$ 同理。于是剩下的问题就是怎么将阶乘分解成上述形式。
考虑计算 $a$:统计 $1,2,\cdots,m$ 中能提取出多少 $p$ 的因子。比较简单,只需要对每个 $p$ 的幂 $p^i$ 统计 $1\sim m$ 中有多少 $p^i$ 的倍数。可以 $O(\log_p m)$ 完成。
再考虑计算 $b$,可以递归计算:
- 先计算出 $1\sim m$ 中所有非 $\mathbf{p}$ 的倍数的数之积模 $p^k$;
- 再将 $p$ 的倍数单独提出来,除以 $p$ 后即为 $1\sim\lfloor\tfrac{m}{p}\rfloor$,递归处理。
可以先预处理出 $f_i$ 表示 $1\sim i$ 中所有不为 $p$ 的倍数的数的积模 $p^k$,则第一步的答案为
现在就可以快速计算组合数了。
对于这道题,可以直接拆开组合数,计算
然后直接用 exLucas 的拆解阶乘的方法,再用CRT合并(就不需要真的去计算每个组合数)。
# 源代码
点击展开/折叠代码
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
史书缺失的那页
遗忘了主角
有人传说这一切
如流光幻夜
——《流光幻夜》By 司夏
> Link 流光幻夜-网易云