思路:数位dp模板题

先跟着灵神学一下 数位dp

然后你就会了...

因为其实就是一个非常裸的数位dp。刷过哪怕一道数位dp的题，你就能够立马反应过来。

在模板的基础上做一个更改:dfs的过程中转移当前数位的最大值$mx$。递归出口返回$mx$即可。

题目内容

在古老的魔法书中，每一个正整数 $n$ 都蕴含着一股魔力，其魔力值 $M(n)$ 定义为 $n$ 在十进制表示下所有数码中的最大值。例如 $M(1012) = \max\{1, 0, 1, 2\} = 2$，$M(988) = \max\{9, 8, 8\} = 9$。

魔法师翻阅了书的第 $x$ 页到第 $y$ 页，他希望计算出这些页码的魔力值总和。由于结果可能非常巨大，请你帮他求出 $\left( \sum_{n=x}^{y} M(n) \right) \bmod 10^9+7$ 的值。

约束条件：页码 $x$ 和 $y$ 满足 $1 \le x \le y \le 10^{18}$。

输入描述

输入包含一行，两个整数 $x$ 和 $y$，表示起止页码。

输出描述

输出一个整数，表示所求魔力总和模 $10^9+7$ 的结果。

样例1

输入

1 10

输出

46

说明

在区间 $[1, 10]$ 内，各个整数的魔力值分别为： $M(1)=1$，$M(2)=2$，$M(3)=3$，$M(4)=4$，$M(5)=5$，$M(6)=6$，$M(7)=7$，$M(8)=8$，$M(9)=9$，$M(10)=1$。 总和为 46。

样例2

输入

99 101

输出

11

说明

我们需要计算 $M(99)$、$M(100)$ 和 $M(101)$。

• $99$ 的数码为 9 和 9，最大是 9，故 $M(99)=9$。
• $100$ 的数码为 1、0、0，最大是 1，故 $M(100)=1$。
• $101$ 的数码为 1、0、1，最大是 1，故 $M(101)=1$。 总和为 11。

样例3

输入

1000000000000000000 1000000000000000000

输出

1

说明

页码 $10^{18}$ 的十进制表示为 1 后面跟着 $18$ 个 0，所有数码中的最大值为 $1$，因此 $M(10^{18})=1$。 由于区间只包含这一个数，总和为 1。