题解 | #小红删数字#

1. 问题分析

题目要求对数组 $a$ 进行 $n-1$ 次操作，每次操作针对数组末尾的两个数进行加法模10或乘法模10，并将结果放回末尾。我们来追踪数组的变化过程（假设数组长度为4，元素为 $a_1, a_2, a_3, a_4$ ）：

操作对象是末尾的 $a_3, a_4$ 。假设运算结果为 $R_1 = (a_3 \oplus_1 a_4) \% 10$ 。数组变为： $[a_1, a_2, R_1]$ 。
操作对象是末尾的 $a_2, R_1$ 。假设运算结果为 $R_2 = (a_2 \oplus_2 R_1) \% 10$ 。数组变为： $[a_1, R_2]$ 。
操作对象是末尾的 $a_1, R_2$ 。假设运算结果为 $R_3 = (a_1 \oplus_3 R_2) \% 10$ 。数组变为： $[R_3]$ 。

由此可见，该操作序列在数学上等价于一个右结合的嵌套表达式： $Result = a_1 \oplus_{n-1} (a_2 \oplus_{n-2} (\dots (a_{n-1} \oplus_1 a_n)\dots))$ 其中，每一个 $\oplus_k$ 都可以独立地选择是加法（ $+$ ）还是乘法（ $\times$ ），且所有运算均在模 10 意义下进行。

数据规模： $n$ 可达 $200,000$ 。这意味着不能使用指数级的暴力搜索（ $2^{n-1}$ 种方案），算法复杂度必须控制在 $O(n)$ 。
状态空间：尽管输入 $a_i$ 很大，但根据模运算性质 $(a \text{ op } b) \pmod{10} = ( (a \pmod{10}) \text{ op } (b \pmod{10}) ) \pmod{10}$ ，我们只需要关注 $a_i \pmod{10}$ 的值。因此，任意时刻中间结果的值域仅为 $[0, 9]$ 。
计算方向：由于运算结构是右结合的（Suffix Structure），即 $a_i$ 总是与 “ $a_{i+1}$ 到 $a_n$ 这个后缀计算出的结果” 进行运算。因此，算法处理顺序应从数组末尾向前遍历。

2. 线性动态规划

鉴于子问题的重叠性质（后缀 $i+1 \dots n$ 的结果无论是由何种操作组合产生，只要最终数值相同，对于 $a_i$ 来说就是等价的），以及最优子结构特性，本题适合采用 动态规划。

状态定义

定义 $dp[i][val]$ 为：仅考虑数组后缀 $a_i, \dots, a_n$ ，经过 $n-i$ 次操作后，最终结果为数字 $val$ ( $0 \le val \le 9$ ) 的方案总数。

状态转移方程

对于位置 $i$ ( $1 \le i < n$ )，其结果依赖于 $a_i$ 与后缀 $i+1$ 的结果 $next\_val$ 进行合并。对于每一个可能的后缀结果 $j \in [0, 9]$ （即 $dp[i+1][j] > 0$ ）， $a_i$ 与 $j$ 有两种组合方式：

加法方案：结果变为 $(a_i + j) \% 10$ 。对新状态的贡献： $dp[i][(a_i + j) \% 10] \ += dp[i+1][j]$
乘法方案：结果变为 $(a_i \times j) \% 10$ 。对新状态的贡献： $dp[i][(a_i \times j) \% 10] \ += dp[i+1][j]$

注意：以上累加过程均需对 $10^9 + 7$ 取模。

边界条件

对于最后一个元素 $a_n$ ，不需要进行操作，它本身就是后缀的结果。 $dp[n][a_n \% 10] = 1$ $dp[n][other] = 0$

3. 代码实现

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

static constexpr ll MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    if (n == 1) {
        for (int i = 0; i <= 9; i++) {
            if (a[0] == i)
                cout << 1 << (i == 9 ? "" : " ");
            else
                cout << 0 << (i == 9 ? "" : " ");
        }
        cout << "\n";
        return 0;
    }

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

    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= 9; j++) {
            int v1 = (a[i] + j) % 10;
            dp[i][v1] = (dp[i][v1] + dp[i + 1][j]) % MOD;
            int v2 = (a[i] * j) % 10;
            dp[i][v2] = (dp[i][v2] + dp[i + 1][j]) % MOD;
        }
    }

    for (int i = 0; i <= 9; i++) {
        cout << dp[0][i] << " ";
    }
    cout << "\n";
}

4. 复杂度分析

时间复杂度

复杂度： $O(N)$
分析：我们需要从 $n-1$ 遍历到 $1$ 。在每一步迭代中，内层循环固定执行 10 次（遍历数字 0-9），且循环体内的操作均为常数级（加法、乘法、取模）。

空间复杂度

复杂度： $O(1)$
分析：虽然输入数组需要 $O(N)$ 的存储，但动态规划的核心逻辑只需要两个长度为 10 的数组来维护状态（滚动数组思想）。
内存对比：相比于 $O(N \times 10)$ 的完整 DP 表格，空间占用极小。

特判

单元素数组：如果 $n=1$ ，操作次数为 0，需特殊处理。