【例3.5】位数问题

题目描述

在所有的 $N$ 位数中，有多少个数中含有偶数个数字 $3$ （ $0$ 个也算偶数个）？输出这个答案对 $12345$ 取余的值。输入一个数 $N$ ，输出对应的答案。

输入样例：

text

输出样例：

text

思路

只关心数字 $3$ 出现次数的奇偶：设允许前导零时长为 $k$ 的串中 $3$ 的个数为偶/奇的个数是 $e_k, o_k$ ，每一位取 $9$ 种非 $3$ 数字则奇偶不变、取 $3$ 则翻转，解递推得 $e_k=\frac{10^k+8^k}{2}$ 、 $o_k=\frac{10^k-8^k}{2}$ 。首位不能为 $0$ ，单独分类： $8$ 种非 $3$ 首位配 $e_{N-1}$ 、首位 $3$ 翻转后配 $o_{N-1}$ ，故答案 $= 8e_{N-1} + o_{N-1} = \frac{9 \cdot 10^{N-1} + 7 \cdot 8^{N-1}}{2}$ 。分子恒为偶数，在模 $2 \times 12345 = 24690$ 下快速幂求出分子后整除 $2$ 再模 $12345$ ，避免“先取模再除 $2$ ”丢失信息。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 04:47
# update_at: 2026-09-30 04:47

import sys

MOD = 12345
HALF = 2 * MOD  # 全程只在模 2*12345 下运算，最后整除 2 就等于对答案做精确减半


def even_count(n: int) -> int:
    """N 位数中含偶数个数字 3 的个数，对 12345 取模。

    允许前导 0 时逐位转移是"9 种非 3 数字保持奇偶 + 数字 3 翻转奇偶"，
    解两状态递推得 偶数个 3 有 e_k=(10^k+8^k)/2 个、奇数个 3 有 (10^k-8^k)/2 个。
    首位换成 1..9（其中只有 3 会翻转奇偶）后：
    答案 = 8*e_{n-1} + o_{n-1} = (9*10^(n-1) + 7*8^(n-1)) / 2。
    """
    doubled = (9 * pow(10, n - 1, HALF) + 7 * pow(8, n - 1, HALF)) % HALF
    return doubled // 2 % MOD  # 括号内恒为偶数，所以整除 2 是真减半而非取整


def solve() -> None:
    n = int(sys.stdin.buffer.read())
    print(even_count(n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 09:11
 * update_at: 2026-10-05 09:11
 */

// 求 N 位数中含偶数个数字 3 的个数，对 12345 取模。
// 逐位转移：这一位取 9 种非 3 数字时奇偶不变，取数字 3 时奇偶翻转。
// 设 e_k、o_k 为允许前导零时长度 k 的串中 3 的个数为偶/奇的个数，
// 递推解耦得 答案 = 8*e[N-1] + o[N-1] = (9*10^(N-1) + 7*8^(N-1)) / 2，
// 用快速幂按闭式直接计算，O(log N)。
#include <cstdio>
using namespace std;
typedef long long ll;

const ll MOD = 12345;
const ll HALF = 2 * MOD; // 分子恒为偶数，在模 2*MOD 下计算后真正整除 2，避免除法丢信息

ll n; // 位数 N

ll read_input() {
    if (scanf("%lld", &n) != 1) return 0;
    return n;
}

// 快速幂：a^e mod p
ll mod_pow(ll a, ll e, ll p) {
    ll result = 1 % p; // p 可能为 1 时结果应为 0
    a %= p;
    while (e > 0) {
        if (e & 1) result = result * a % p;
        a = a * a % p;
        e >>= 1;
    }
    return result;
}

void solve() {
    // 分别在模 HALF 下求 10^(N-1)、8^(N-1)，中间乘 9/7 后仍在 ll 范围内
    ll pow10 = mod_pow(10, n - 1, HALF);
    ll pow8 = mod_pow(8, n - 1, HALF);
    ll doubled = (9 * pow10 % HALF + 7 * pow8 % HALF) % HALF; // 分子 9*10^(N-1)+7*8^(N-1)
    ll ans = doubled / 2 % MOD; // 分子恒为偶数，先整除 2 再取模
    printf("%lld\n", ans);
}

int main() {
    if (read_input() == 0) return 0;
    solve();
    return 0;
}