这么简洁的题目当然不用数位 DP 啦。
将 \(n\) 搞成 \(10\) 的幂次之和计算。比如说 \(1234\) 就拆成 \(1\sim 4,1\sim 30,1\sim 200,1\sim 1000\) 来计算。枚举后缀长度 \(i\),除去最高位外剩下每一位都可以填除 \(7\) 以外的任何数字,所以它的贡献即为 \(9^{i-1}\) 再乘上最高位能填的数字。这里能填的数字是指不为 \(7\) 并且小于最高位的数字,究其原因就是用 \(x000\ldots 000\) 替代 \((x-1)000\ldots 000\) 进行计算。
不过这样处理会导致最高位数字为 \(7\) 时多算一次,减掉就行了。
不过因为题目中保证了 \(n\) 中不存在 \(7\) 所以没有关系。不过我们可以很轻松地把做法拓展到对 \(n\) 没有限制:如果除去当前枚举的后缀外前面还有 \(7\),当前后缀的贡献记为 \(0\) 即可。
标签:P1590,数字,后缀,000,失踪,ldots,sim From: https://www.cnblogs.com/landsol/p/17773691.html