题解

思路

把答案按“前导 1 的第几个位置”拆开：一个数若有 $k$ 个前导 1，就会分别给前缀 1、11、……、长度为 $k$ 的全 1 前缀贡献一次。

做法

固定全 1 前缀 $p$ 和总位数后，符合条件的数构成区间 $[p\cdot10^t,(p+1)\cdot10^t-1]$，把它与 $[1,N]$ 的交集长度加入答案即可。

复杂度

全 1 前缀长度和补在其后的位数都只有 $O(\log N)$ 种，因此枚举所有区间的时间复杂度为 $O(\log^2N)$，空间复杂度为 $O(1)$；区间端点用足够宽的整数计算可避免溢出。