题目思路

考虑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)。

代码

Python

x = input()
n, mod = len(x), 10**9+7
f = [0] * 10
f[int(x[0])] = 1
for i in range(1, n):
    c = int(x[i])
    f[c] = (sum(f) - f[c] + 1) % mod
print((sum(f) + mod) % mod)

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String x = scanner.nextLine();
        int n = x.length();
        int mod = 1000000007;
        
        // 初始化f数组
        long[] f = new long[10];
        f[Character.getNumericValue(x.charAt(0))] = 1;

        // 循环计算
        for (int i = 1; i < n; i++) {
            int c = Character.getNumericValue(x.charAt(i));
            long sumF = 0;
            for (long value : f) {
                sumF = (sumF + value) % mod;
            }
            f[c] = (sumF - f[c] + 1 + mod) % mod;
        }

        // 计算并输出结果
        long result = 0;
        for (long value : f) {
            result = (result + value) % mod;
        }
        System.out.println((result + mod) % mod);

        scanner.close();
    }
}

c++

# include<bits/stdc++.h>

using namespace std;
typedef long long ll; // 答案都要取模，肯定要用long long
const int mod = 1e9 +7;

int main(){
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<ll>> dp(n, vector<ll>(10, 0));
    dp[0][s[0]-'0'] = 1;

    for (int i=1;i<n;i++){
        for (int j = 0; j<10; j++){
            if (s[i] - '0' == j){
                int sum = 0;
                for(int j = 0; j<10; j++){
                    sum = (sum + dp[i-1][j]) % mod;
                }
                dp[i][j] = (sum - dp[i-1][j] +1 + mod)% mod;
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    ll ans = 0;
    for (int j=0; j<10; j++){
        ans = (ans + dp[n-1][j]) % mod;
    }

    cout << ans;

}

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

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

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

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

输入描述

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

输出描述

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

样例

输入

12121

输出

9