2026-01-20-牛客每日一题-小红删数字

title: 2026-01-20-牛客每日一题-小红删数字
date: 2026-01-20
tags:

• 算法学习
• 牛客
• 动态规划

题目信息

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

题目描述

给定长度为 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>usingnamespacestd;usingll=longlong;constintN=2e5+5;constll MOD=1000000007;ll n,t,a[N],cnt[N][10];intmain(){cin>>n;for(inti=1;i<=n;++i){cin>>t;if(n>1)a[i]=t%10;elsea[i]=t;// 特判 n = 1}cnt[n][a[n]]++;//初始化,dp的起点for(inti=n;i>1;--i){for(intj=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(inti=0;i<10;++i){cout<<cnt[1][i]<<' ';}return0;}

总结与反思

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