MegaFactorial

前言：更符合人类的做法，比大多数题解少一个 $k$。

MegaFactorial ​

给定 $f(n,k)$。有 $f(0,k)=1,f(n,0)=n,f(n,k)=f(n-1,k)\times f(n,k-1)$

计算 $f(n,k)$ 在 $b$ 进制下末尾 $0$ 的个数，答案对 ${10}^9+9$ 取模（warn）。

$n\in [1,{10}^9],k\in [1,16],b\in [2,10]$。

性质 ​

1. 看成过河卒问题，则只需计算 $f(n,0)$ 一列的贡献，调用过河卒问题公式可计算贡献次数。比如数字 $i(i\le n)$ 对 $f(n,k)$ 贡献是 $i^{(\genfrac{}{}{0ex}{}{n-i+k-1}{k-1})}$。最后的数的确切值即 $\prod _{i=1}^n{i}^{(\genfrac{}{}{0ex}{}{n-i+k-1}{k-1})}$ 。

2. 考虑在 $b$ 进制下末尾 $0$ 的个数如何刻画，可以证明奇质因子的个数一定小于质因子 $2$ 的个数*，故按照 $B$ 分类讨论：

你要找最大的 $m$ 使得，$B^m|ans$ ，所以如果是本身是质数则直接取自己就行，如果是 $6$ 则取 $3$，$10$ 则取 $5$ 做，如果是 $p^c$ 则取 $p$ 做，答案取 $ \lfloor \frac{m}{c} \rfloor $ 就行。

思路 ​

接下来开始做题。

现在题目是：找到 $\prod _{i=1}^n{i}^{(\genfrac{}{}{0ex}{}{n-i+k-1}{k-1})}$ 的给定质因子 $p_0=2\mathrm{或}3\mathrm{或}5\mathrm{或}7$ 的个数。

那么改写为 $\sum _{i=1}^n(\genfrac{}{}{0ex}{}{n-i+k-1}{k-1})v(i)$，$v(i)$ 为 $i$ 含 $p_0$ 的个数，枚举$p_0^t$，$\sum _{t\ge 1}^{{\log }_{p_0}n}\sum _{j=1}^{\frac{n}{p_0^t}}(\genfrac{}{}{0ex}{}{n-j{p}_0^t+k-1}{k-1})$。

这时候注意看 $(\genfrac{}{}{0ex}{}{n-j{p}_0^t+k-1}{k-1})$ 自变量只有 $j$，把组合数暴力拆开就是一个关于 $j$ 的多项式，次数至多（因为是模意义下）是 $k-1$，求和就是次数为 $k$ 的多项式，我们用拉插来求出这个多项式，复杂度就是 $k^2\log n$ 的，当然这个复杂度没有计算逆元的 $\log$，所以总复杂度就是 $k^2{\log }^{2}n$。

据说此时有神秘矩乘做法，但是很非人类了。

细节 ​

如果是 $p^c$ 则取 $p$ 做，答案要取 $ \lfloor \frac{m}{c} \rfloor $ ，但是我们要取模，考虑怎么做向下取整。

考虑同余，令 $m=ac+b$，最后我们要的答案就是 $a$，即 $a=\frac{m-b}{c}$。，$b=m\mathrm{mod}c$ 是好做的。

代码 ​

补充证明 ​

• 结果 $ans$ 奇质因子的个数一定小于质因子 $2$ 的个数: