题目信息

  • 平台：牛客
  • 题目：小红删数字
  • 难度：中等
  • 题目链接

题目描述

给定长度为 n 的数字序列 a1…an，每一步在相邻两个数之间选择加号或乘号，并对结果取模 10，按从左到右的顺序计算。请统计最终结果为 0..9 的方案数，对 1e9+7 取模输出。

初步思路

  1. 从右往左做 DP：设 cnt[i][v] 表示从位置 i 到 n 的子序列，最终结果为 v 的方案数。
  2. 右端初始化：cnt[n][a[n]] = 1。
  3. 转移：把 a[i-1] 与 cnt[i][*] 的结果通过 + 或 * 合并，更新 cnt[i-1][*]。

算法分析

  • 核心：右向左 DP，枚举每个位置与后缀结果的加法/乘法
  • 技巧：结果只关心 0..9，因此状态数固定为 10
  • 时间复杂度：O(10n)
  • 空间复杂度：O(10n)

代码实现（C++）

#include <iostream>
using namespace std;

using ll = long long;

const int N = 2e5 + 5;
const ll MOD = 1000000007;

ll n, t, a[N], cnt[N][10];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> t;
        if (n > 1)
            a[i] = t % 10;
        else
            a[i] = t; // 特判 n = 1
    }
    cnt[n][a[n]]++;//初始化,dp的起点
    for (int i = n; i > 1; --i) {
        for (int j = 0; j < 10; ++j) {
            cnt[i - 1][(a[i - 1] + j) % 10] =
                (cnt[i - 1][(a[i - 1] + j) % 10] + cnt[i][j]) % MOD;
            cnt[i - 1][(a[i - 1] * j) % 10] =
                (cnt[i - 1][(a[i - 1] * j) % 10] + cnt[i][j]) % MOD;
        }
    }
    for (int i = 0; i < 10; ++i) {
        cout << cnt[1][i] << ' ';
    }
    return 0;
}

总结与反思

  1. 结果只和个位相关，状态压缩到 10 个值即可。
  2. 右向左推导能避免重复计算，直接统计所有结果分布。