题解 | 小红删数字

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    static final int N = 200005;
    static int[] arr = new int[N];
    static int[][] dp = new int[N][10];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            int t = in.nextInt();
            arr[i] = (n > 1) ? t % 10 : t;
        }

        // dp[i][j]：合并到剩余 i 个数，且合并结果为 j 的方案数
        // 注意，当 n = 1 且 arr[1] > 9 时，无法合并，所以不能初始化直接跳过
        if (n == 1 && arr[1] > 9){
            for (int i = 0; i < 10; i++) System.out.print(dp[1][i] + " ");
            return;
        }
        
        // 初始化未开始合并，结果就只能是 arr[n] % 10
        // 即 dp[n][arr[n] % 10] = 1 ，方案数为 1
        dp[n][arr[n] % 10]++;

        // 状态转移
        // 操作① ：dp[i][(arr[i] + j) % 10] += dp[i+1][j],  0 <= j <= 9 (作为上一次合并的结果)
        // 合并到剩余 i 个数，结果为 (当前数 + 上一次合并的结果 % 10) 的方案数 = ∑ dp[i+1][j] （对上次合并结果为 j 的求和）
        
        // 操作②：dp[i][(arr[i] * j) % 10] += dp[i+1][j]
        // 合并到剩余 i 个数，结果为 (当前数 * 上一次合并的结果 % 10) 的方案数 = ∑ dp[i+1][j] （对上次合并结果为 j 的求和）
        for (int i = n; i > 1; i--) {
            for (int j = 0; j <= 9; j++) {
                dp[i - 1][(arr[i - 1] + j) % 10] = (dp[i - 1][(arr[i - 1] + j) % 10] + dp[i][j]) % MOD;
                dp[i - 1][(arr[i - 1] * j) % 10] = (dp[i - 1][(arr[i - 1] * j) % 10] + dp[i][j]) % MOD;
            }
        }
        for (int i = 0; i < 10; i++) System.out.print(dp[1][i] + " ");
    }
}