题意

求区间 \([L,R]\) 中所有数的所有数位上数字的出现次数。

分析

首先预处理出 \(f[i][j][k]\) 表示长度为 \(i\) 位,最高位为 \(j\) 的所有数中,数字 \(k\) 的出现次数。

然后分三种情况:

  • 比当前数位数小的数
  • 第一位比当前数小,位数相同的数

这两类都可以通过预处理的 \(f[i][j][k]\) 得到。

第三类就是第一位相同,第一位和第二位都相同 \(\cdots \cdots \)

可以通过不断去掉有一位,不断逼近得到。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注