小红删数字

[题目链接](https://www.nowcoder.com/practice/1287555d90d34de3be4ae338b18c1fbd)

思路

每次操作取数组最后两个数 $a$ 和 $b$ ，删除后将 $(a+b) \bmod 10$ 或 $(a \times b) \bmod 10$ 放回末尾。操作 $n-1$ 次后只剩一个数。问最终结果为 $0, 1, \ldots, 9$ 的方案数各是多少。

关键观察

由于每次操作的结果都取个位数，后续运算也只关心个位数，因此整个过程只和每个数的个位有关。

操作顺序是固定的：每次取最后两个元素，所以第一次操作一定是合并 $a_{n-1}$ 和 $a_{n-2}$ ，第二次是合并结果与 $a_{n-3}$ ，以此类推。合并的顺序从右往左是确定的，每步只有加法或乘法两种选择。

DP 定义

设 $dp[d]$ 表示当前从右侧已处理的元素合并后，结果个位为 $d$ 的方案数。

初始状态： $dp[a_{n-1} \bmod 10] = 1$ 。

转移：从 $i = n-2$ 到 $i = 0$ ，对每个当前个位 $d$ ，可以通过加法得到 $(v + d) \bmod 10$ ，或通过乘法得到 $(v \times d) \bmod 10$ ，其中 $v = a_i \bmod 10$ 。

$ $dp'[(v + d) \bmod 10] \mathrel{+}= dp[d]$ $

$ $dp'[(v \times d) \bmod 10] \mathrel{+}= dp[d]$ $

特判

当 $n = 1$ 时没有操作，剩余数字就是 $a_0$ 本身。若 $a_0 \in [0, 9]$ ，则对应位置方案数为 $1$ ；否则所有位置均为 $0$ 。

复杂度

时间复杂度： $O(10n)$ ，每个元素对 10 个可能的个位进行转移。
空间复杂度： $O(10)$ ，只需维护长度为 10 的 DP 数组。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    if (n == 1) {
        for (int i = 0; i < 10; i++) {
            printf("%d%c", a[0] == i ? 1 : 0, i == 9 ? '\n' : ' ');
        }
        return 0;
    }

    vector<long long> dp(10, 0);
    dp[a[n - 1] % 10] = 1;

    for (int i = n - 2; i >= 0; i--) {
        vector<long long> ndp(10, 0);
        int v = a[i] % 10;
        for (int d = 0; d < 10; d++) {
            if (dp[d] == 0) continue;
            ndp[(v + d) % 10] = (ndp[(v + d) % 10] + dp[d]) % MOD;
            ndp[(v * d) % 10] = (ndp[(v * d) % 10] + dp[d]) % MOD;
        }
        dp = ndp;
    }

    for (int i = 0; i < 10; i++) {
        printf("%lld%c", dp[i], i == 9 ? '\n' : ' ');
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        final int MOD = 1000000007;

        if (n == 1) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 10; i++) {
                if (i > 0) sb.append(' ');
                sb.append(a[0] == i ? 1 : 0);
            }
            System.out.println(sb.toString());
            return;
        }

        long[] dp = new long[10];
        dp[a[n - 1] % 10] = 1;

        for (int i = n - 2; i >= 0; i--) {
            long[] ndp = new long[10];
            int v = a[i] % 10;
            for (int d = 0; d < 10; d++) {
                if (dp[d] == 0) continue;
                ndp[(v + d) % 10] = (ndp[(v + d) % 10] + dp[d]) % MOD;
                ndp[(v * d) % 10] = (ndp[(v * d) % 10] + dp[d]) % MOD;
            }
            dp = ndp;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            if (i > 0) sb.append(' ');
            sb.append(dp[i]);
        }
        System.out.println(sb.toString());
    }
}