题目思路

本题关键在于：相邻数位两两不同，那么也就意味着，对于任意一个数$c$，我们需要更新集合的大小，一定是在集合中寻找不是以$c$为结尾的那些子序列，然后往它们后面增加一个$c$ ，放入集合中.

此时我们定义状态:$dp[i][j]$ 代表考虑了前$i$个数位，并且结尾为数字$j(0 \leq j \leq 9)$ 的子序列个数。

转移:

假设当前位置$i$的数字为$c$

本题为2024年4月13日美团实习开发岗机考原题

美团机考的介绍点击这里

题目描述

小美有一个数字串$x$，她将$x$的所有非空子序列都取了出来，将其中满足相邻数位两两不同的子序列都加入了集合$S$ 中。

她想知道集合$S$的大小最终有多大，请你帮她计算一下吧。

(注意:根据数学知识我们知道，集合中的元素具有互异性，即两两不同) (在本题中，子序列可以存在前导0，也就是说如“011”和“00011”是不同的)

输入描述

输入包含一行一个数字串 $x(0 \le x\le10^{1000000})$，表示塔子哥的数字$x$。 ($x$可能含有前导 0)

输出描述

输出包含一行一个整数，表示集合的大小。 (由于结果可能很大，因此你只要输出答案对 1000000007取的结果)

样例

输入

12121

输出

9