1301 位数问题
1301 位数问题
【算法】 递推、组合数学
【C++】 数组、循环、取模
【难度】 普及−
一、题目简述
在所有的 位数中,有多少个数包含偶数个数字 3?答案对 取模。
例如 时,两位数的范围是 ,其中包含偶数个 3 的有:
- 含 0 个 3:除 3 外的 8 个十位 除 3 外的 9 个个位 个
- 含 2 个 3:只有 , 个
- 共 个。
数据范围: 可能较大,因此需要取模 。
二、解题思路
2.1 拆解问题
一个 位数可以看作:首位(不能是 )+ 后 位(可以是 )。
关键观察:当我们向一个数的末尾添加一位数字时,3 的个数奇偶性如何变化?
2.2 状态定义
定义两个数组(先考虑允许前导零的情况):
| 符号 | 含义 |
|---|---|
| 位数(允许前导零)中,有偶数个 3 的个数 | |
| 位数(允许前导零)中,有奇数个 3 的个数 |
边界:(空串含 0 个 3,0 是偶数),。
2.3 递推关系
现在我们思考:已知 位的情况,怎么推出 位的情况?
操作很简单——在 位的末尾再拼一位数字,可选 共 10 种。这 10 种选择分为两类:
| 末尾加什么 | 有几种 | 对"3 的个数"的影响 |
|---|---|---|
| 非 3 数字(0,1,2,4,5,6,7,8,9) | 9 种 | 3 的个数不变,奇偶性不变 |
| 数字 3 | 1 种 | 3 的个数 +1,奇偶性翻转 |
怎么来?( 位数中,含偶数个 3)
要拼出偶数个 3,有两种来源:
| 来源 | 解释 | 方案数 |
|---|---|---|
| 位已经偶数个 3,末尾加非 3 | 偶数 + 没加 3 = 还是偶数 | |
| 位是奇数个 3,末尾加 3 | 奇数 + 加一个 3 = 变成偶数 |
怎么来?( 位数中,含奇数个 3)
同理:
| 来源 | 解释 | 方案数 |
|---|---|---|
| 位已经奇数个 3,末尾加非 3 | 奇数 + 没加 3 = 还是奇数 | |
| 位是偶数个 3,末尾加 3 | 偶数 + 加一个 3 = 变成奇数 |
用 验证一下:
从 (空串)出发:。
含义:1 位数(允许前导零,即 0~9)中,偶数个 3 的有 共 9 个;奇数个 3 的只有 共 1 个。✓
用 再验证一步:
从 出发:
含义:2 位数(允许前导零,即 00~99)中,偶数个 3 的有 82 个,奇数个 3 的有 18 个。总数 ,合理。✓
💡 一句话总结:状态转移的关键是——加非 3 数字奇偶性不变(),加数字 3 奇偶性翻转()。
2.4 首位特殊处理
位数的首位不能是 0,只有 9 种选择(1~9):
- 首位选非 3(8 种:1,2,4,5,6,7,8,9)→ 后 位需要偶数个 3
- 首位选3(1 种)→ 后 位需要奇数个 3
2.5 手动验证
| 计算 | 答案 | |||
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 |
验证 :1 位数中(1~9),含偶数个 3 的是 ,共 8 个。✓
每一步都对 取模,防止溢出。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 12345;
int main() {
int n;
cin >> n;
// f[0][0] = 1, f[0][1] = 0(空串:0 个 3,偶数)
int f0 = 1; // 偶数个 3
int f1 = 0; // 奇数个 3
// 递推 N-1 次,得到后 N-1 位的状态(允许前导零)
for (int i = 1; i <= n - 1; i++) {
int new_f0 = (f0 * 9 + f1 * 1) % MOD;
int new_f1 = (f0 * 1 + f1 * 9) % MOD;
f0 = new_f0;
f1 = new_f1;
}
// 处理首位(不能为 0)
int ans = (8 * f0 + 1 * f1) % MOD;
cout << ans << endl;
return 0;
}另一种写法(数组版)
如果觉得变量轮换不够直观,用二维数组更清晰:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 12345;
const int N = 1e5 + 5;
int f[N][2]; // f[i][0]: 偶数个3, f[i][1]: 奇数个3
int main() {
int n;
cin >> n;
f[0][0] = 1;
f[0][1] = 0;
for (int i = 1; i <= n - 1; i++) {
f[i][0] = (f[i - 1][0] * 9 + f[i - 1][1] * 1) % MOD;
f[i][1] = (f[i - 1][0] * 1 + f[i - 1][1] * 9) % MOD;
}
int ans = (8 * f[n - 1][0] + 1 * f[n - 1][1]) % MOD;
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,一次循环递推。
- 空间复杂度:(变量轮换版)或 (数组版)。
五、思维拓展
本题的核心技巧是状态递推——把"偶数个 3"和"奇数个 3"作为两个状态,每次加一位数字时,状态之间相互转移。这种"双状态转移"的模式在许多计数问题中都会出现,例如:
- 走楼梯,每次走 1 或 2 步,但不能连续走 2 步
- 01 序列中不含连续 1 的个数
六、易错点
- 首位不能是 0:不要在递推过程中忘记这个约束。先算"允许前导零"的 ,再对首位的 9 种选择分别处理。
- 边界 :循环 to 不会执行,,答案 ,结果正确。
- 取模时机:每一步递推都要
% MOD,否则中间结果可能溢出int。
七、其他说明
本节从"往前插位"的角度重新推导,作为对 2.3 和 2.4 节的补充,帮助理解递推的双向性。
7.1 非最高位递推(允许前导零)
设 表示 位数字串(允许前导零)中含偶数个 3 的数量, 表示含奇数个 3 的数量。
这次换一个方向:在长度为 的串前面新增一位数字,共 10 种选择。
推导 :
| 原串状态 | 新增位选什么 | 贡献 |
|---|---|---|
| 偶数个 3 | 非 3(9 种:0,1,2,4,5,6,7,8,9) | |
| 奇数个 3 | 数字 3(1 种) |
推导 (同理):
与 2.3 节"往后拼"的结果一致,说明无论从哪头加数字,递推关系不变。
7.2 最高位单独处理
位正整数最高位不能为 0。先用递推算完后 位(允许前导零)的 和 ,再拼接合法最高位:
| 最高位选择 | 种类数 | 后 位需要 | 贡献 |
|---|---|---|---|
| 非 3(1,2,4,5,6,7,8,9) | 8 种 | 偶数个 3 | |
| 数字 3 | 1 种 | 奇数个 3(因为最高位多了一个 3) |
