问题：位数问题

任务总览

题目描述

在所有的 N 位数中，有多少个数中有偶数个数字 3？由于结果可能很大，你只需要输出这个答案对 12345 取余的值。

问题说明

• N 位数是由 1 到 9 的数字构成（第一位不能是 0），因此共有 9^N 种可能的数字。
• 需要计算这些 N 位数中，数字 3 出现偶数次的个数，并输出对 12345 取余的结果。

输入格式

• 一个整数 N，1 ≤ N ≤ 1000，表示数字的位数。

输出格式

• 输出一个整数，表示含偶数个数字3的N位数个数对 12345 取余的结果。

输入输出示例

输入示例 1

2

输出示例 1

73

解释

• 在所有的 2 位数字中：
  • 72 个数字包含 0 个 3。
  • 1 个数字包含 2 个 3。
  • 总共 73 个数字符合要求。

题目分析

目标

计算 N 位数中，数字 3 出现偶数次的个数，并取 12345 余数。

思路

• 设 dp[i][j] 表示长度为 i 的数字中，3 出现了 j 次的个数。
• 递推：
  • 当前位不是 3：继承上一个状态，即 dp[i][j] += dp[i-1][j] * 8（有 8 种选择）。
  • 当前位是 3：使 j 增加 1，即 dp[i][j] += dp[i-1][j-1]。
• 目标值是所有 dp[N][j]，其中 j 是偶数。

时间复杂度分析

• ​状态空间​：O(N^2)
• ​计算复杂度​：O(N^2)
• ​空间复杂度​：O(N^2)

结论

本题核心是通过动态规划计算含偶数个数字 3 的 N 位数数量，并取 12345 余数作为答案。