#9669. 位数问题
位数问题
问题:位数问题
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
位数问题 | 1000 ms | 256 MiB | 10 points |
题目描述
在所有的 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
个数字符合要求。
- 72 个数字包含 0 个
题目分析
目标
计算 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
余数作为答案。