首页 > 试题广场 >

小红删数字

[编程题]小红删数字

热度指数：2522 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数数组 $a_1,a_2,\dots,a_n$ 。需要进行恰好 $n-1$ 次操作，数组最终只剩下一个数字。

$\hspace{15pt}$ 每次操作只能针对当前数组的最后两个数 $x,y$ （ $x$ 在前， $y$ 在后）执行下述二选一：
$\hspace{23pt}\bullet\,$ 将 $x,y$ 删除，并将 $\bigl(x+y\bigr) \bmod 10$ 插入到数组末尾；
$\hspace{23pt}\bullet\,$ 将 $x,y$ 删除，并将 $\bigl(x\times y\bigr) \bmod 10$ 插入到数组末尾。

$\hspace{15pt}$ 请统计，在所有可能的操作序列下，最终结果为 $0,1,\dots,9$ 的方案数各有多少。答案对 $10^9+7$ 取模。

输入描述:

第一行输入整数 ——数组长度。

第二行输入  个整数 ——初始数组。

输出描述:

输出一行  个整数，第  个数表示最终结果为  的方案数（按 ）。

示例1

输入

4
1 2 3 4

输出

1 0 0 0 3 3 0 0 0 1

算法知识视频讲解

C++

kilomatutinal

喵呜~主人不会这道题喵？其实只需要会dp就可以做出来了喵！

我们可以“从后往前思考”喵！

这里dp数组就像猫猫的“记忆小本本”，记录着当前状态下个位数为0-9的方案数。开始时只考虑最后一个数字，所以它的个位数位置记为1喵~

对于每个新数字，猫猫会检查所有可能的个位数组合，并用新的小本本记录喵！

每次处理完一个数字，就用新的“记忆小本本”替换旧的，继续向前探索喵~

举个猫猫栗子喵！

假设数字是 [2, 3, 4]：
1.开始：只考虑4 → dp[4] = 1
2.加入3：与4组合产生7(加)和2(乘) → dp[7] = 1, dp[2] = 1
3.加入2：与7组合产生9(加)和4(乘)，与2组合产生4(加)和4(乘)
4.最终：dp[4] = 3, dp[9] = 1（其他都是0喵）

这种方法避免了重复计算喵每次只关心个位数，大大简化了问题喵~
下面可以看代码喵！

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    vector<ll> dp(10,0);

    if(n==1)//只有一个元素时
    {
        if(a[0]<10) dp[a[0]]=1;//如果该元素小于10，就有范围内方案
        for(int i=0;i<10;i++) cout << dp[i] << ' ';//直接输出
        return 0;
    }

    dp[a[n-1]%10]=1;//初始化：将最后一位加入dp中

    for(int i=n-2;i>=0;i--)
    {
        vector<ll> xin(10,0);//新形态数组
        int now=a[i]%10;//当前数的个位数
        for(int j=0;j<10;j++)
        {
            //加法操作：(now+j)%10
            int jia=(now+j)%10;
            xin[jia]+=dp[j];
            xin[jia]%=mod;
            //乘法操作：(now*j)%10
            int cheng=(now*j)%10;
            xin[cheng]+=dp[j];
            xin[cheng]%=mod;
        }
        dp=xin;
    }
    for(int i=0;i<10;i++) cout << dp[i] << ' ';

}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

发表于 2026-01-20 01:08:32 回复(0)

Kato_Shoko

噗嗤——这种一眼就能看出是倒排动态规划（DP）的题目，居然还有杂鱼在纠结？逻辑简单到连路边的牛都能秒懂吧？

既然你们这些大脑空空的家伙还在搜索题解，本天才少女翔子就勉为其难地给你们讲讲。好好听着，这可是杂鱼们唯一的救赎机会哦！详情可看**************************

📊 翔子的天才课堂：后缀归并 DP

🧐 核心逻辑：别被“最后两个数”骗了！

题面说每次操作“最后两个数 ”，这意味着什么？这意味着这个数组的合并顺序是从右往左固定的！

想象一下，你有一排数字。

第一次操作一定是合并和，变成一个新数。
第二次操作一定是合并和刚才那个新数。
...以此类推。

这不就是个简单的后缀处理吗？如果你连这个合并顺序都看不出来，建议直接把杂鱼❤键盘捐给有需要的人，呵呵❤~

💡 DP 状态定义

我们只需要记录：处理到第个数字时，后面所有数字合并出的结果为的方案数分别有多少。

状态：dp[i][j] 表示从第个数到第个数，合并后的结果为的方案数。
转移：当我们把加入合并时，它会和后面已经合并出的结果进行加法或乘法：
加法：new_val = (a[i] + j) % 10
乘法：new_val = (a[i] * j) % 10
dp[i][new_val] += dp[i+1][j]

这种的复杂度，简直是闭着眼都能跑过，只有没用的❤杂鱼❤才会担心超时吧❤？

💻 毫无难度的 C++ 代码

这里的代码宏定义写得这么多，真是杂鱼最后的倔强呢❤~

#include <bits/stdc++.h>
#define il inline
#define double long double
using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128 = __int128_t;

const ll N = 5e5 + 5, mod = 1e9+7, inf = 2e18;
const double eps = 1e-9;
double PI = 3.1415926;

il void solve(){
    int n;
    cin>>n;
    if(n==1){
        ll a;
        cin>>a;
        for(int i=0;i<10;i++){
            cout<<(i==a%10?1:0)<<' ';
        }
        return ;
    }
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=10; // 杂鱼记得取模，不然爆掉就搞笑了
    }
    // 这个DP表大得离谱，不过谁让内存不值钱呢
    vector<vector<ll>>dp(n+5,vector<ll>(10));
    dp[n][a[n]]=1;

    for(int i=n-1;i>=1;i--){
        for(int j=0;j<10;j++){            
            // 乘法合并，智商乘法也是0吗？
            ll ed=j*a[i]%10;
            (dp[i][ed]+=dp[i+1][j])%=mod;

            // 加法合并，像不像在数自己的失误次数？
            ed=(j+a[i])%10;
            (dp[i][ed]+=dp[i+1][j])%=mod;
        }
    }
    for(int i=0;i<10;i++){
        cout<<dp[1][i]<<" ";
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--){
        solve();
    }
    return 0;
}

🐍 慢悠悠的 Python 代码

Python 的处理速度虽然像杂鱼爬行一样慢，但写起来倒是挺省事的❤。

import sys

# 这种递归深度设置，杂鱼是不是想把内存撑爆呀？
sys.setrecursionlimit(1145141919)
input = sys.stdin.readline

def read():
    line = sys.stdin.readline()
    if not line: return []
    return list(map(int, line.split()))

mod = 10**9 + 7

def solve():
    n_list = read()
    if not n_list: return
    n = n_list[0]

    a = [0] + read()
    if n == 1:
        # 只有一个数的情况，❤杂鱼❤一定要看清楚题哦
        for i in range(10):
            print(1 if a[1] % 10 == i else 0, end=' ')
        return

    for i in range(n + 1):
        a[i] %= 10

    # 简单的二维数组，❤杂鱼❤能学会吗？
    dp = [[0] * 10 for i in range(n + 5)]
    dp[n][a[n]] = 1

    for i in range(n - 1, 0, -1):
        for j in range(10):
            if dp[i+1][j] == 0: continue

            # 乘法转移
            ed = j * a[i] % 10
            dp[i][ed] = (dp[i][ed] + dp[i + 1][j]) % mod

            # 加法转移
            ed = (j + a[i]) % 10
            dp[i][ed] = (dp[i][ed] + dp[i + 1][j]) % mod

    for i in range(10):
        print(dp[1][i], end=' ')

def main():
    t = 1
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

🙄 翔子的最后叮嘱

看完了吗？看完了就赶紧拿着这份代码去提交，❤杂鱼❤别再盯着屏幕发呆了！

这种后缀合并的思路，只要稍微带点脑子就能想到。要是下次还问这种水平的题，翔子真的会忍不住笑出声来的，呵呵❤~ 明白了吗？杂鱼们！

编辑于 2026-01-20 15:48:26 回复(0)

C++

驴主

DP. Python 写完 AI 转 C++. 


#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MOD = 1e9 + 7;
const int DIGIT = 10;  // 数字0-9的范围

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> arr(n);

    if(n == 1){
        int x;
        cin >> x;
        for(int i = 0; i < 10; i++){
            int y = 0;
            if(x == i) y = 1;
            cout << y << ' ';
        }
        cout << endl;
        return 0;
    }
    

    // 读取输入并处理：取每个数的最后一位（对应Python的lambda x: int(x[-1])）
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        arr[i] = s.back() - '0';  // 字符串最后一位转数字（char转int）
    }

    // 定义三维DP数组：dp[i][j][k]
    // 维度：[n][DIGIT][DIGIT]，初始值全为0
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(DIGIT, vector<int>(DIGIT, 0)));

    // 初始化dp[0]：前0个数（第一个数）的状态
    for (int i = 0; i < DIGIT; ++i) {
        int add = (i + arr[0]) % 10;
        int mul = (i * arr[0]) % 10;
        dp[0][i][add] = (dp[0][i][add] + 1) % MOD;
        dp[0][i][mul] = (dp[0][i][mul] + 1) % MOD;
    }

    // 状态转移：迭代计算dp[i][j][k]
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < DIGIT; ++j) {
            for (int k = 0; k < DIGIT; ++k) {
                // 计算转移的前驱状态
                int prev_add = (j + arr[i]) % 10;
                int prev_mul = (j * arr[i]) % 10;
                // 状态转移：累加前驱状态的结果并取模
                dp[i][j][k] = (dp[i-1][prev_add][k] + dp[i-1][prev_mul][k]) % MOD;
            }
        }
    }

    // 输出结果：dp[n-2][arr.back()] 的所有元素
    for (int k = 0; k < DIGIT; ++k) {
        cout << dp[n-2][arr.back()][k] << " ";
    }
    cout << endl;

    return 0;
}

发表于 2026-01-20 00:59:12 回复(0)

提交观点

问题信息

难度：

3条回答 13收藏 58浏览