AT_arc127_a 题解

在 HL 群里吃瓜，顺手写一篇题解。

第一眼必定是数位 dp，可是这会使原题难度反而升高了。相对而言，我们要是枚举前缀 \(1\) 的长度，然后寻找对答案有贡献的区间，此问题是很容易的。同时我们不难发现，前缀 \(1\) 长度为 \(l\) 的所有有贡献的数字即为 \(\forall i\in[l,16],(\sum_{i=0}^l10^i)\times10^{16-l}\sim (2+\sum_{i=1}^l10^i)\times10^{16-l}\)。枚举计算即可。

代码没几行，不放了。注意前边那一大堆式子本质上是一堆连续的 \(1\)，因此可以迭代计算而不用每次重新计算。