题解 P2529 【[SHOI2001]击鼓传花】

说真的 大佬的题解真的太意识流了(两篇) 对蒟蒻来说能坚持到看明白需要勇气啊。。对蒟蒻真的是不友善。。 或许怎么说。。。 这就是大佬吧。 首先公式给出，与那位大佬V2.0版中的公式相同。设 $f(x)$ 表示 $x!$ 最后一个非0的数，那么有 $$f(x)=f(x/5)×a(x \% 20)$$ $a$ 是预设的数组。 首先嘛 不要考虑 $10^{100}$ 这么大的数。来考虑一些友善的数据范围，比如 $100000$ 这么大之类的。这个怎么做呢？ 如果求某一个数 $x$ 的最后一位那谁都会：$x\%10$。如果求的是某一个数 $x$ 的最后一位非0的数，在 $x/10$ 能算的出来的时候，$while(x\%10==0) x/10$ 再 $\%10$ 就好了。 注意这两点：$x×y\%10=(x\%10)×(y\%10)$。 $10$ 等于 $2×5$ 并且 $2,5$ 都是质数。 那么现在把 $x!$ 表示为 $c×2^{a}×5^{b}$。( $c$ 不包含质因子 $2$ 和 $5$ ) 显然 $a>b$ 。~~(这里显然没问题吧)~~ 所以最后的结果应该为 $2^{a-b}×c\%10$。 想到这里我们就可以用约为 $O(n)$ 级别的时间来计算这个解了。初始化 $ans=1$ ，对于从 $1$ 到 $x$ 的每一个数，都除尽它的 $2$ 因子与 $5$ 因子，记下 $a-b $ 的值，除干净了把这个数 $\%10$ 并乘上 $ans$ ，最后 $ans$ 乘一下 $(a-b)$ 个 $2$ ，就能得到结果。 我们显然可以优化这个过程。 先把所有的 $5$ 的倍数都拿出来放到一边，一会乘起来。原数组会变成类似 $$1,2,3,4,1,6,7,8,9,1,11,12,13,14,1,16,17,18,19,1,21,22 ...$$ 这样。 考虑像分块一样把每 $10$ 个数作为一组。假想我们有一种方式，能将几个数相乘后的结果中的 $10$ 预先抽离出来，将它变成 $$(1×2×3×4×1×6×7×8×9×1\%10+10×q_1)$$ $$×$$ $$(1×2×3×4×1×6×7×8×9×1\%10+10×q_2)$$ $$×$$ $$...........$$ $$×$$ $$(1×2×3×4×1×6×7×8×9×1\%10+10×q_n)$$ 这个样子。 很显然如果不提 $2$ ，每一段乘起来 $\%10$ 的值都是相同的 $6$ 。 当然提 $2$ 之后也是相同的。每 $10$ 个数，拿走两个 $2$ 来和提取出的两个 $5$ 的倍数值进行匹配，无论 $q_i$ 的值如何(即使是 $0$ )，每组 $\%10$ 后的值都将变成 $4$ 。 现在就变成了，很多个 $4$ 乘起来，乘最后没完整划分为 $10$ 个数的那一组，乘上一堆之前提出的 $5$ 的倍数再 $/5$ 的值，的最后一位非 $0$ 值是多少。什么是"一堆之前提出的 $5$ 的倍数再 $/5$ 的值"? 就是说提出的 $5,10,15,20,25,30...$ 这些数，每一个 $/5$ ，提出的 $5$ 与提出的 $2$ 乘在一起变成 $10$ 扔掉，就变成了 $1×2×3×4×5×6×....$ 这一共有 $x/5$ 个数。也就是 $4^{?}×$*最后的那几个分不了组的数*$ × f(x/5)$ $4×4\%10=6$ 。~~聪明的~~你会发现，对于 $x!$ 的最后一个非 $0$ 数，一定是偶数，换句话说就是 $2,4,6,8$ 中的一个。 $6*2\%10=2$，$6*4\%10=4$，$6*6\%10=6$，$6*8\%10=8$。 $6$ 与能成为答案的数相乘都是不改变值的*所以我们干脆每20个数分成一组*，每一组为原来的两组，提出 $2$ 和 $5$ 之后的值是 $6$ 。 $6$ 与任何一个答案值乘在一起是不会变的，所以我们可以当做没看见。 对于最后面的几个数显然是可以预处理的。所以现在答案变成了 $6^{?}×$ *预处理* $ × f(x/5)=$ *预处理* $ × f(x/5)$ 把预处理的数组放到 $a$ 上面就好了。 也就是说如果你理解了的话，$a$ 数组是 $$1,2,3,4,\frac{1}{2},6,7,8,9,\frac{1}{2}....$$ 的前缀和。不对，前缀乘（ $\%10$ ）。 所以代码几乎是只要维护一个~~区区~~ $100$ 位的高精除。复杂度 $O(n^2log_510)$ 。我写的太丑，就不放了。