位数问题（CSP-J 数学递推 / 动态规划）

一、题目描述

在所有的 N 位数中，有多少个数满足：

数字 3 出现的次数是偶数次。

由于答案可能很大，只需要输出答案对：

12345

取余后的结果。

---

二、问题说明

一个 N 位数：

• 每一位可以是数字 1~9；
• 第一位不能为 0；
• 因此共有：

$9^N$

个不同的 N 位数。

现在要求统计：

其中数字 3 出现次数为偶数的数字数量。

---

三、输入格式

输入一个整数：

N

表示数字的位数。

---

四、输出格式

输出一个整数：

表示满足条件的数字数量：

$\pmod {12345}$

后的结果。

---

五、数据范围

1 ≤ N ≤ 1000

---

六、样例

输入

2

---

输出

73

---

七、样例解释

所有两位数：

第一位：

1~9

第二位：

0~9

共有： $9\times10=90$ 个两位数。

---

要求：

数字 3 出现偶数次。

可能情况：

---

情况1：没有数字3

第一位：

1,2,4,5,6,7,8,9

共有：

8种

第二位：

0,1,2,4,5,6,7,8,9

共有：

9种

所以： $8\times9=72$

情况2：出现两个数字3

只有：

33

一种。

---

所以答案： $72+1=73$ 输出：

73

---

八、错误思路分析

暴力枚举

例如：

N=1000

数字数量： $9^{1000}$

无法枚举。

所以需要寻找规律。

---

九、解题思路

关键：

只关心：

当前数字中，3出现次数的奇偶性。

不用知道具体出现几次。

定义状态：

---

状态0：偶数个3

例如：

没有3

33

3333

---

状态1：奇数个3

例如：

3

333

33333

---

每增加一位：

只有两种变化：

---

添加一个不是3的数字

奇偶性不变：

偶数 → 偶数

奇数 → 奇数

---

添加一个数字3

奇偶性改变：

偶数 → 奇数

奇数 → 偶数

---

十、状态转移

设：

dp0[i]

表示：

长度为 i 的数字中：

3出现偶数次的数量。

dp1[i]

表示：

长度为 i 的数字中：

3出现奇数次的数量。

---

第一位

长度1：

数字：

1 2 3 4 5 6 7 8 9

其中：

数字3：

奇数次：

3

数量：

[ dp1[1]=1 ]

其他：

偶数次：

1 2 4 5 6 7 8 9

数量：

[ dp0[1]=8 ]

---

十一、状态转移公式

增加一个数字：

新的偶数状态

来源：

原来的偶数 + 非3数字

非3数字：

10个数字：

0,1,2,4,5,6,7,8,9

共9个。

贡献：

$dp0[i-1]\times9$

原来的奇数 + 数字3

贡献： $dp1[i-1]$

所以：

$dp0[i]=dp0[i-1]\times9+dp1[i-1]$

---

新的奇数状态

来源：

原来的奇数 + 非3数字

$dp1[i-1]\times9$

原来的偶数 + 数字3

$dp0[i-1]$

所以：

$dp1[i]=dp1[i-1]\times9+dp0[i-1]$

---