别样的组合数大战

· · 算法·理论

求 \dbinom {n}{m} \bmod p^k 的结果，保证 p 为素数且 p\le 10，k\le 23，n,m\le 10^{18}。

首先尝试套用 exLucas 的方法，先求出 n!,m!,(n-m)! 中 p 的幂数，然后尝试求出 (n!)_p 即 n! 去除所有 p 模 p^k 的结果。

显然有 (n!)_p = ((n/p)!)_p\times f((n/p)-1)\times \prod_{i=(n/p)*p+1}^n i。

其中我们设 f(n)=\prod_{i=0}^n \prod_{j=1}^{p-1} (pi+j)。

不难发现若能在较优的时间复杂度内计算出 f，则能解决问题。

注意到模数为 p^k，故在 f 的积式中若选择了 \ge k 项 pi 则在模意义下为 0，于是我们可以设 g_{n,i} 表示在 f(n) 中，有 i 个括号还未选择的乘积的和，而我们要求的即为 g_{n,0}，显然 g_{n,i} 若要转移到 g_{n,0} 至少要乘 p^i，故 i<k。

这里考虑用类似分治的方法，先求出 f(n/2) 和 g_{n/2}，然后我们需要给右边的分治 f 的括号中整体加一个 ip，这可以乱做，把两个 g 组合起来也是容易的，做加法卷积即可。

求 g_0 可以枚举 1 到 p-1 的每个数是否选择，在 \mathcal O(2^p) 内预处理。

这就做完了，复杂度 \mathcal O(2^p+(p+k^2\log n)\log n)。

直观感觉可能会有大量 g 重复计算，于是把 g 进行记忆化后速度飞起。