考虑dp,设f[i][c]表示前i个字符组成的以c为结尾的合法子序列个数。
假设当前位为j,由于要去重,前面所有以j结尾的子序列对于当前位来说同样可以构造,所以只需要考虑前一位不是以j结尾的答案,同时注意当前这一位可以单独放一个算子序列,所以加上1。
所以转移方程f[i][j] = sum(f[i]) - f[i - 1][j] + 1,最后统计sum(f[n - 1])即可。
由于dp转移只需要考虑前一位,所以可以优化空间复杂度为O(1)。
小美有一个数字串x,她将x的所有非空子序列都取了出来,将其中满足相邻数位两两不同的子序列都加入了集合S 中。
她想知道集合S的大小最终有多大,请你帮她计算一下吧。
(注意:根据数学知识我们知道,集合中的元素具有互异性,即两两不同) (在本题中,子序列可以存在前导0,也就是说如“011”和“00011”是不同的)
输入包含一行一个数字串 x(0≤x≤101000000),表示小美的数字x。 (x可能含有前导 0)
输出包含一行一个整数,表示集合的大小。 (由于结果可能很大,因此你只要输出答案对 1000000007取的结果)
输入
12121
输出
9