题目链接

题意:令 S(i) 表示将 i 的数位从小到大排序后形成的数。例如 S(50394)=3459。给定整数 n,求 S(1)+…+S(n)。对 10^9+7 取模。


考虑一个排过序的数对答案的贡献:

122344

可以拆成

111111

  11111

     111

       11

也就是说,对于数 i,如果有 x 个数大于等于它,可以贡献\(o(x)\),即 x 个 1。

所以一个 dp 策略是 令 f[i][j][k][l] 表示当前确定了前 i 位,有 j 位>=k,是否小于 n 的状态为 l 的方案数。这么做是 \(n^2\) 的(字符集大小视为常数)

换一个做法,考虑枚举数位对答案的贡献,假设目前考虑数位为 d,到第 i 位,枚举下一个数放什么

记 A 为目前贡献的和,B 为目前贡献的方案数

还是考虑这个例子

122344

可以拆成

111111

  11111

     111

       11

现在在后面加一个 5,即

1111111

  111111

     1111

       111

就是原来那个乘 10+5

所以直接维护 AB 两个量即可,这么做就是\O(n)\的了

 


一个非常弱的准退役OIER