题解 P1492 【猩猩散步】

RainFestival · 2019-02-03 16:15:52 · 题解

update on \sf 2021.12.22

以下定义 x\in P 为 x 是质数。

这个题目让我们求 \binom{n+m}{m}\bmod 10^{100}。

显然需要高精度计算。如果你使用朴素的高精，(n+m)! 可能会达到 10^5!，大概有 400000 多位。

这个 400000 多位是对它取对数得到的，\log_{10}(10^5!)\approx 456573.45。

朴素高精乘法很慢，对于两个位数为 n 的数相乘，相当于暴力卷积，是 \mathcal{O(n^2)} 的，不能在本题限制内解决问题。

更重要的是，还要涉及到高精度除法。

所以我们要换一种做法。

我们把 [1,n+m] 中的每一个质数数找出来，然后考虑每一个质数出现了多少次。

我们知道 \binom{n+m}{m}=\frac{(n+m)!}{n!m!}。

假设 p\in P，f_p=(n+m)! 的唯一分解中 p 的次数，a_p=n! 的唯一分解中 p 的次数，b_p=m! 的唯一分解中 p 的次数。

那么答案为 \prod\limits_{p\in P}p^{f_p-a_p-b_p}。

记录 s_p=f_p-a_p-b_p，考虑求出 s。

对于分子部分，每一个质因数的贡献是 +1，对于分母，则是 -1。

我们知道 n 以内的质数数量 $\pi(n)\approx \frac{n}{\ln n}