#9669. 位数问题

位数问题

问题:位数问题


任务总览

任务名称 时间限制 内存限制 分数
位数问题 1000 ms 256 MiB 10 points

题目描述

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

问题说明

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

输入格式

  • 一个整数 N1 ≤ 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)

结论

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