题解 | #小红删数字#

题目链接

小红删数字

题目描述

小红有一个包含 $n$ 个整数的数组。她需要进行 $n-1$ 次操作，直到数组只剩下一个数。

每次操作的规则如下：

选择数组的最后两个数，记为 $x$ 和 $y$ 。
将它们从数组中删除。
选择以下两种方式之一，将结果放回数组的末尾：
- 将 $(x+y)$ 的个位数放回。
- 将 $(x \cdot y)$ 的个位数放回。

问：对于 0 到 9 中的每一个数字 $d$ ，最终剩下的数等于 $d$ 的方案数是多少？答案对 $10^9 + 7$ 取模。

解题思路

1. 分析操作模式

题目规定每次操作都作用于数组的最后两个元素。这个特性揭示了操作的固定顺序：运算是从数组的末尾开始，逐步向开头合并的。

例如，对于数组 [a_1, a_2, a_3, a_4]：

首先合并 a_3 和 a_4，得到结果 r_1。数组变为 [a_1, a_2, r_1]。
接着合并 a_2 和 r_1，得到 r_2。数组变为 [a_1, r_2]。
最后合并 a_1 和 r_2，得到最终结果。

这个过程可以看作是从右到左的链式计算： $op_1(a_1, op_2(a_2, op_3(a_3, a_4)))$ ，其中每个 $op$ 都是加法或乘法（对10取模）。

2. 动态规划解法

这种具有清晰阶段和顺序的计数问题，是动态规划的典型应用场景。

状态定义

我们定义一个 dp 数组，dp[j] 表示将当前已处理的数组后缀合并成一个数，且这个数的个位数为 $j$ 的方案数。
特殊情况 (n=1)

如果数组只有一个元素 a_1，那么不需要进行任何操作，最终的数就是 a_1 本身。题目要求统计结果为 0-9 的方案数。因此，如果 a_1 恰好在 [0, 9] 区间内，那么得到 a_1 的方案数是 1，得到其他数字的方案数是 0。如果 a_1 不在这个区间内（例如 a_1 = 11），那么得到 0-9 中任何一个数字的方案数都是 0。
状态转移 (n>1)

我们从数组的最后一个元素开始，从右向左遍历。
1. 基本情况：当只处理最后一个元素 $a_n$ 时，由于它将与左边的元素进行运算，我们只关心它的个位数。因此，处理后缀 a[n:] 的结果是 $a_n \pmod{10}$ ，方案数为 1。我们的 dp 数组初始化为 dp[a_n % 10] = 1，其余为 0。
2. 递推：当我们从右向左处理到第 $i$ 个元素 $a_i$ 时，我们需要用 $a_i$ 与已经处理完的后缀 a[i+1:] 的所有可能结果进行合并。
  
  假设 dp 数组中存储的是处理完后缀 a[i+1:] 的结果。现在，我们创建一个临时的 new_dp 数组来存放处理完后缀 a[i:] 的结果。
  
  令 $x = a_i \pmod{10}$ 。
  
  遍历后缀 a[i+1:] 的所有可能结果 $y$ （从 0 到 9）：
  - 如果 dp[y] > 0，说明有 dp[y] 种方案可以得到结果 $y$ 。
  - 我们可以用 $x$ 和 $y$ 进行两种运算：
    - 加法：新结果为 $d_{add} = (x + y) \pmod{10}$ 。这为 new_dp 中得到 $d_{add}$ 的方案数增加了 dp[y] 种。
    - 乘法：新结果为 $d_{mul} = (x \cdot y) \pmod{10}$ 。这为 new_dp 中得到 $d_{mul}$ 的方案数增加了 dp[y] 种。
  遍历完所有的 $y$ 后，new_dp 就代表了处理完后缀 a[i:] 的结果。我们用 new_dp 更新 dp，然后继续向左处理下一个元素。
最终结果

当遍历完整个数组后，dp 数组中 dp[0], dp[1], ..., dp[9] 就是最终的答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        int val = a[0];
        for (int i = 0; i < 10; ++i) {
            cout << (i == val ? 1 : 0) << (i == 9 ? "" : " ");
        }
        cout << endl;
        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> new_dp(10, 0);
        int current_num = a[i] % 10;

        for (int j = 0; j < 10; ++j) {
            if (dp[j] > 0) {
                long long ways = dp[j];

                // 加法
                int add_res = (current_num + j) % 10;
                new_dp[add_res] = (new_dp[add_res] + ways) % MOD;

                // 乘法
                int mul_res = (current_num * j) % 10;
                new_dp[mul_res] = (new_dp[mul_res] + ways) % MOD;
            }
        }
        dp = new_dp;
    }

    for (int i = 0; i < 10; ++i) {
        cout << dp[i] << (i == 9 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;

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();
        }
        
        if (n == 0) {
            return;
        }

        if (n == 1) {
            int val = a[0];
            for (int i = 0; i < 10; i++) {
                System.out.print((i == val ? 1 : 0) + (i == 9 ? "" : " "));
            }
            System.out.println();
            return;
        }

        final int MOD = 1_000_000_007;

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

        for (int i = n - 2; i >= 0; i--) {
            long[] newDp = new long[10];
            int currentNum = a[i] % 10;

            for (int j = 0; j < 10; j++) {
                if (dp[j] > 0) {
                    long ways = dp[j];

                    // 加法
                    int addRes = (currentNum + j) % 10;
                    newDp[addRes] = (newDp[addRes] + ways) % MOD;

                    // 乘法
                    int mulRes = (currentNum * j) % 10;
                    newDp[mulRes] = (newDp[mulRes] + ways) % MOD;
                }
            }
            dp = newDp;
        }

        for (int i = 0; i < 10; i++) {
            System.out.print(dp[i] + (i == 9 ? "" : " "));
        }
        System.out.println();
    }
}

import sys

def solve():
    MOD = 10**9 + 7
    try:
        n_str = sys.stdin.readline()
        if not n_str:
            return
        n = int(n_str)
        a = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    if n == 0:
        return

    if n == 1:
        val = a[0]
        ans = [0] * 10
        if 0 <= val <= 9:
            ans[val] = 1
        print(*ans)
        return
        
    dp = [0] * 10
    dp[a[n - 1] % 10] = 1

    for i in range(n - 2, -1, -1):
        new_dp = [0] * 10
        current_num = a[i] % 10
        
        for j in range(10):
            if dp[j] > 0:
                ways = dp[j]
                
                # 加法
                add_res = (current_num + j) % 10
                new_dp[add_res] = (new_dp[add_res] + ways) % MOD
                
                # 乘法
                mul_res = (current_num * j) % 10
                new_dp[mul_res] = (new_dp[mul_res] + ways) % MOD
        
        dp = new_dp
        
    print(*dp)

solve()

算法及复杂度

算法：动态规划
时间复杂度： $O(N)$ 。
- 我们从右到左遍历数组一次，对于数组中的 $N-1$ 个元素，我们都需要进行一次状态转移。
- 每次状态转移需要遍历大小为 10 的 dp 数组，这是一个常数时间的操作。因此总时间复杂度为 $O(N \cdot 10) = O(N)$ 。
空间复杂度： $O(N)$ 。
- 主要的空间开销来自于存储输入的长度为 $N$ 的数组。DP 状态的存储只需要常数空间（两个大小为 10 的数组）。