思路：数位DP

定义 $dp(i,mask,isLimit,isNum)$ 表示构造第 $i$ 位及其之后的数位的合法方案数

$mask$ 表示前面选过的数字集合，换句话说，第 $i$ 位要选的数字不能出现在 $mask$ 中
$isLimit$ 表示当前是否受到了 $n$ 的约束。若为真，则第 $i$ 位填入的数字至多为 $s[i]$ ，否则可以是 $9$
$isNum$ 表示 $i$ 前面是否填了数字，若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1（不允许出现前导0）；若为真，则要填入的数字可以从 0 开始。

P1598.第3题-饱餐一顿

1000ms

Difficulty: 10

所属公司 : 阿里

算法与标签>动态规划

“非常的新鲜，非常的美味”，这是我修院对美食的极大赞赏。

如何定义一道美食为美味呢，我塔子百思不得其解，我修院解释道：假设一道美食有一个美味值，当且仅当它的相邻数位都不相同。例如:114514是不美味的，但1919810则美味的很呐！

塔子有些困惑，想做更多的尝试（大悲），他想知道，美味值不大于x的美食中有多少道是美味的?

答案对 $10^9+7$ 取模。

一个正整数 $x$ , $1$ $<$ $x$ $<$ $10^{100000}$

不大于 $x$ 的美味的菜的数量，对 $10^9+7$ 取模

输入

输出

说明

不大于15的正整数中，只有11是不美味的

1s, 1024KiB for each test case.

编辑器加载中…

输入

预期输出（选填）