题目思路

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

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

转移:

题目内容

小美手头握着数字串 $w$ ，先枚举 $w$ 里每一个非空的子序列，再把相邻位上数字均互不相等的那些放进集合 $P$ 。

请帮忙求出集合 $P$ 最终会含有多少个元素。

(提醒:集合按定义不允许重复成员，彼此必须不一样) (本题把子序列当成数字字符序列看待，允许开头为 $0$ ，因此“203”与“00203”并不相同)

仅有一行，给出数字串 $w(0 \le w\le10^{1000000})$ ，即塔子哥手里的数字 $w$ 。 ( $w$ 允许以 $0$ 打头)

向标准打印一个整数，即该集合的元素个数。 (答案或许很大，故仅需打印该值模 $1000000007$ 之后的余数)

输入

输出

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写

选择提交后点击「开始AI分析」