尾零组合数

令$T(m,k)$是所有满足$k\le n\le m$且能被10整除的组合数$\binom{n}{k}$的数量。 可以验证$T(10^9, 10^7-10)=989697000$。 求$T(10^{18}, 10^{12}-10)$。

本题难度:

解答

令A为上述范围内不能被5整除的组合数的数量，B为其中不能被2整除的组合数的数量，那么所欲求的结果是 $$10^{18}-10^{12}+10-|A|-|B|+|A\cap B|.$$ 类似于第320题，设t是满足$p^t\le n! < p^{t+1}$，那么$n!$中p的幂是 $$\lfloor\frac{n}{p}\rfloor+\ldots+\lfloor\frac{n}{p^t}\rfloor$$ 依次对$n!, k!, (n-k)!$使用这一公式，可得当仅当k的p进展开中的各位数字都不超过n的p进展开中的各位数字时$\binom{n}{k}$不能被p整除（即Lucas定理）。 $10^{12}-10$的5进展开是$112340444444444430_5$，共有18位。 因此每一位数字都不小于它的18位5进制数有4800个（每一位有$5-d$种可能，d取遍各位数字后相乘），而$10^{18}/5^{18}=2^{18}$，从而 $$|A|=4800\times 2^{18}.$$ 同理，$10^{12}-10$的2进展开$1110100011010100101001010000111111110110_2$，共40位，其中有18个0。 因此每一位数字都不小于它的40位2进制数有$2^{18}$个，而$10^{18}$除$2^{40}$的商是909494，余数为$771607494656 < 10^{12}-10$，从而 $$|B|=2^{18}\times 909494.$$ 最后，注意到A中的每个n模$5^{18}$只有上述4800种可能，B中的每个n模$2^{18}$只有上述$2^7=128$种可能（$10^{12}-10$的2进展开中最后18位只有7个0）。 由中国剩余定理，只需考察 $$x=a\cdot 5^{18}+b\cdot 2^{18}$$ 模$10{18}$是否在$A\cap B$中，共有$4800\times 128$种可能，可以检验（对应的程序简单，此处略）其中有$321$种符合要求，因此结果是 $$10^{18}-10^{12}+10-(4800+909494)\cdot 2^{18}+321=999998760323313995.$$ 本题无需编程。