@994495jj
2017-08-13T12:00:37.000000Z
字数 294
阅读 776
cfgym100443F
201708 （ACM）动态规划----数位dp
- 对于n!，它末尾的0个数由2和5贡献。显然2的个数大于5的个数，于是只要考虑5的贡献。
- n!的所有5的贡献是n/5+n/25+n/125+...。于是判断n!0个数的奇偶转为判断n/5+n/25+n/125+...的奇偶。
- 将n写成五进制，于是/5操作相当于右移。
- 五进制数和它的数位之和同奇偶。
- n/5+n/25+n/125+...中，n的偶数位出现偶次，奇数位出现奇次。于是判断n/5+n/25+n/125+...的奇偶转为判断n的奇数位之和的奇偶。
- 问题转为0~n中有多少数的五进制表示奇数位之和是偶数。数位dp求解即可。
