题目链接
[小红删数字]https://www.nowcoder.com/practice/a246d1e2b38e454985ac1400591d6175
题目描述
给定一个长度为 的整数数组
。需要进行恰好
次操作,直到数组中只剩下一个数字。
每次操作固定地针对当前数组的最后两个数 (
在前,
在后)进行,并二选一执行:
- 将
删除,并将
的结果插入到数组末尾。
- 将
删除,并将
的结果插入到数组末尾。
请统计在所有可能的操作序列下(即每次操作的两种选择),最终结果为 的方案数各有多少。答案需要对
取模。
解题思路
1. 分析操作结构
操作的顺序是固定的,总是从数组的末尾开始。我们来分析一下 的情况,数组为
:
- 第一次操作: 对
操作,结果为
。数组变为
。
- 第二次操作: 对
和第一次的结果
操作,结果为
。数组变为
。
- 第三次操作: 对
和第二次的结果
操作,最终结果为
。
这种固定的操作顺序产生了一种嵌套的表达式结构。这启发我们从后向前进行动态规划。关键在于,所有中间和最终结果都在 的范围内。
2. 动态规划设计
我们可以定义一个DP状态来表示对数组的一个后缀进行计算后,所有可能的结果及其对应的方案数。由于结果只可能是 ,DP状态可以是一个大小为10的数组。
-
状态定义:
是一个大小为10的数组。
表示对数组后缀
进行所有可能的运算后,结果为
的方案数。
-
状态转移: 我们要计算
,可以利用
的结果。
存储了对后缀
运算的所有结果的方案数。现在我们引入
,它将与
中的每一个结果进行一次
+
或*
的运算。具体来说,对于
中的每一个可能的结果
,它有
种方案。这
种方案都会为
贡献两种新结果:
- 加法: 新结果为
。
- 乘法: 新结果为
。
所以,我们可以通过遍历
来计算
:
dp[i] = array of size 10, initialized to 0 for j from 0 to 9: count = dp[i+1][j] if count > 0: dp[i][(a_i' + j) % 10] += count dp[i][(a_i' * j) % 10] += count
- 加法: 新结果为
-
基本情况: 从数组的最后一个元素开始,当只考虑后缀
时,没有操作可进行,所以结果只有一个,就是
本身,方案数为 1。 因此,
是一个大小为10的数组,只有
的值为1。
-
最终结果: 我们从
向下迭代到
,最终
中就存储了对整个数组进行运算后,得到
的方案数。
-
特殊情况 n=1: 当
时,需要进行
次操作,这意味着数组的初始状态即为最终状态。最终结果就是数组中唯一的数
。题目要求统计
的方案数。因此,如果
恰好在此区间内,则结果
的方案数为1;否则,所有我们关心的结果 (
) 的方案数都为0。
代码实现
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
const int MOD = 1000000007;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n == 1) {
vector<int> result(10, 0);
if (a[0] >= 0 && a[0] <= 9) {
result[a[0]] = 1;
}
for (int i = 0; i < 10; ++i) {
cout << result[i] << (i == 9 ? "" : " ");
}
cout << endl;
return 0;
}
// dp[j] 表示当前后缀运算结果为 j 的方案数
vector<int> dp(10, 0);
// 基本情况:处理 a[n-1]
dp[a[n - 1] % 10] = 1;
// 从后向前递推
for (int i = n - 2; i >= 0; --i) {
vector<int> next_dp(10, 0);
int current_val = a[i] % 10;
for (int j = 0; j < 10; ++j) {
if (dp[j] > 0) {
// (a[i] + j) mod 10
int res_add = (current_val + j) % 10;
next_dp[res_add] = (next_dp[res_add] + dp[j]) % MOD;
// (a[i] * j) mod 10
int res_mul = (current_val * j) % 10;
next_dp[res_mul] = (next_dp[res_mul] + dp[j]) % MOD;
}
}
dp = next_dp;
}
for (int i = 0; i < 10; ++i) {
cout << dp[i] << (i == 9 ? "" : " ");
}
cout << endl;
return 0;
}
import java.util.Scanner;
public class Main {
private static final int MOD = 1_000_000_007;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
if (n == 1) {
int[] result = new int[10];
if (a[0] >= 0 && a[0] <= 9) {
result[(int)a[0]] = 1;
}
for (int i = 0; i < 10; i++) {
System.out.print(result[i] + (i == 9 ? "" : " "));
}
System.out.println();
return;
}
// dp[j] 表示当前后缀运算结果为 j 的方案数
int[] dp = new int[10];
// 基本情况:处理 a[n-1]
dp[(int)(a[n - 1] % 10)] = 1;
// 从后向前递推
for (int i = n - 2; i >= 0; i--) {
int[] nextDp = new int[10];
int currentVal = (int)(a[i] % 10);
for (int j = 0; j < 10; j++) {
if (dp[j] > 0) {
// (a[i] + j) mod 10
int resAdd = (currentVal + j) % 10;
nextDp[resAdd] = (nextDp[resAdd] + dp[j]) % MOD;
// (a[i] * j) mod 10
int resMul = (currentVal * j) % 10;
nextDp[resMul] = (nextDp[resMul] + dp[j]) % MOD;
}
}
dp = nextDp;
}
for (int i = 0; i < 10; i++) {
System.out.print(dp[i] + (i == 9 ? "" : " "));
}
System.out.println();
}
}
import sys
def main():
MOD = 1_000_000_007
try:
n_str = sys.stdin.readline()
if not n_str: return
n = int(n_str)
a = list(map(int, sys.stdin.readline().split()))
except (IOError, ValueError):
return
if n == 1:
result = [0] * 10
if 0 <= a[0] <= 9:
result[a[0]] = 1
print(*result)
return
# dp[j] 表示当前后缀运算结果为 j 的方案数
dp = [0] * 10
# 基本情况:处理 a[n-1]
dp[a[n - 1] % 10] = 1
# 从后向前递推
for i in range(n - 2, -1, -1):
next_dp = [0] * 10
current_val = a[i] % 10
for j in range(10):
if dp[j] > 0:
# (a[i] + j) mod 10
res_add = (current_val + j) % 10
next_dp[res_add] = (next_dp[res_add] + dp[j]) % MOD
# (a[i] * j) mod 10
res_mul = (current_val * j) % 10
next_dp[res_mul] = (next_dp[res_mul] + dp[j]) % MOD
dp = next_dp
print(*dp)
if __name__ == "__main__":
main()
算法及复杂度
- 算法: 动态规划
- 时间复杂度:
,其中
是数组的长度,
是可能的结果数量。外层循环
次,内层循环遍历大小为
的DP数组。总复杂度为
,可以简化为
。
- 空间复杂度:
。主要开销是存储输入数组
。DP数组的空间是
,是常数级别的。