首页 > 试题广场 >

小红删数字

[编程题]小红删数字

热度指数：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

算法知识视频讲解

kilomatutinal

发表于 2026-01-20 01:09:47

喵呜~主人不会这道题喵？其实只需要会dp就可以做出来了喵！我们可以“从后往前思考”喵！这里dp数组就像猫猫的“记忆小本本”，记录着当前状态下个位数为0-9的方案数。开始时只考虑最后一个数字，所以它的个位数位置记为1喵~对于每个新数字，猫猫会检查所有可能的个位数组合，并用新的小本本记录喵！每次处理完一展开全文

yunayu

发表于 2026-01-20 01:04:47

讲讲思路最近做了各种dp，DAG上dp，分层dp，换根dp，AC自动机上dp......所以看到这道题第一眼就发现这是一个无后效性的线性递推。为什么是线性？因为某一轮各结果的方案数完全取决于上一轮各结果的方案数。不难发现，本题虽然比较大，但模数特别小，所以可以实现的状态转移。如何构展开全文

Minazuki_Hotaru

发表于 2026-01-20 05:03:00

动态规划考虑，操作完第项后，结果为的方案数，每一轮操作的数字会变成和，不难写出转移方程我们在转移的时候开一个辅助数组tmp去滚，dp的第一维可以省略掉，时间复杂度，注意的时候，大于等于的数字不能算在计数里，下面贴代码 /* ## ## ####### ######## 展开全文

BeauWill

发表于 2026-01-20 11:27:17

考虑线性dp状态设计为dp[i][j]，表示考虑了后i个元素，结果为j的所有方案数我们发现dp[i+1][(a[i+1]+j)%10]和dp[i+1][(1LL*a[i+1]*j)%10]可以从dp[i][j]转移过来，转移方式就是前者直接加上后者的值，估转移方程为dp[i+1][(a[i+1]+j 展开全文

丨阿伟丨

发表于 2025-09-01 14:37:18

题目链接 [小红删数字]https://www.nowcoder.com/practice/a246d1e2b38e454985ac1400591d6175 题目描述给定一个长度为的整数数组。需要进行恰好次操作，直到数组中只剩下一个数字。每次操作固定地针对当前数组的最后两个数（在前展开全文

Kato_Shoko

发表于 2026-01-20 15:43:38

噗嗤——这种一眼就能看出是**倒排动态规划（DP）**的题目，居然还有杂鱼在纠结？逻辑简单到连路边的牛都能秒懂吧？既然你们这些大脑空空的家伙还在搜索题解，本天才少女翔子就勉为其难地给你们讲讲。好好听着，这可是杂鱼们唯一的救赎机会哦！详情可看【1月20日牛客每日一题【C++/Python】】📊 翔展开全文

此在Dasein

发表于 2026-01-20 01:10:26

1. 问题分析题目要求对数组进行次操作，每次操作针对数组末尾的两个数进行加法模10或乘法模10，并将结果放回末尾。我们来追踪数组的变化过程（假设数组长度为4，元素为）：操作对象是末尾的。假设运算结果为。数组变为：。操作对象是末尾的。假设运算结果为。数组变为：。操作对展开全文

Turgen

发表于 2026-01-20 03:33:10

先看题意，只对后2位操作，再看数据范围，这大概是一个O(n)或O(nlogn)复杂度的题目，但由于题目不允许排序，这样会破坏后2位的位置，所以大概是一个O(n)的做法，题目要求计数，脑海里想到了是否是某数学题目，但题目要求不太可能是，先从小范围考虑。若n=1，此时当且仅当a[1]=i的方案数为1，其展开全文