题目描述
有 $n$ 件礼物，打算送给 $m$ 个人，其中送给第 $i$ 个人的礼物数量为 $w_i$，求送出礼物的方案数，输出答案模 $p$ 的结果，无解输出 $Impossible$。
设 $p=p_1^{c_1}p_2^{c_2}p_3^{c_3}\dots p_t^{c_t}$，$p_i$ 为质数。$1\le n\le 10^9$，$1\le m\le 5$，$1\le p_i^{c_i}\le 10^5$。
算法分析
以为是水题，看来我还是 naive……
首先不难发现答案就是 $C_n^{w_1}C_{n-w_1}^{w_2}\dots C_{n-w_1-w_2-\dots w_{m-1}}^{w_m}$，考虑如何计算这个式子。
$m$ 比较小，直接枚举计算每个组合数的值乘起来就是最终的答案，由于 $n$ 较大，$p$ 不一定为质数，每个组合数的值看起来不那么好算。
考虑 ExLucas 定理？由于 Lucas 定理的前提是模数为质数，而每个质因子上的指数可能大于 $1$，因此无法分解模数后 Lucas 定理再使用中国剩余定理合并。
这样 Lucas 定理的部分就只能直接算了，还是考虑分解模数然后用中国剩余定理合并，要保证数与模数互质才能用扩展欧几里得算法求出该数的逆元套用组合数公式，所以把阶乘中的 $p_i$ 提取出来，同时计算 $n!\mod p_i^{k_i}$ 剩下的部分。
记 $s_i=p_i^{k_i}$，可以将 $n!$ 分解一下，有 $\lfloor\frac{n}{p_i}\rfloor$ 个数是 $p_i$ 的倍数，这部分将他们都除以 $p_i$ 后就变成了 $\lfloor\frac{n}{p_i}\rfloor!$，是原问题的子问题，递归下去就可以了。剩下的不为 $p_i$ 倍数的部分应该怎么算呢？可以发现一个性质，那就是每 $s_i$ 个数（包含 $p_i$ 的倍数）中剩下的数乘积为定值，求出多少这样的块，乘方一下然后对后面不满的块单独计算就好了。
时间复杂度大概是 $O(5\times 20^2\times 10^5)$，不太好分析，总之肯定能过的。
参考题解：CSDN。
代码实现
1 |
|