解题思路

统计 N 位数中含有偶数个数字 3 的个数。N 最大 1000，结果很大，对 12345 取余。

思路：递推。

设：

• a0 = 当前位数中含偶数个 3 的个数
• a1 = 当前位数中含奇数个 3 的个数

每增加一位，有两种选择：

• 这一位选 3（1 种）：奇偶性翻转
• 这一位不选 3（9 种，0~9 去掉 3）：奇偶性不变

所以：

• 新 a0 = a0×9 + a1（上一位偶数 + 选非3保持偶数；上一位奇数 + 选3变成偶数）
• 新 a1 = a1×9 + a0

注意最高位： 最高位不能是 0，所以最高位不选 3 时只有 8 种（去掉 0 和 3）。

1 位数的特殊情况： 1 位数就是 1~9（不含 0），所以要去掉 0 开头的情况。

举例：2 位数

• 偶数个 3 = 0 个 3（首位 8 种 × 次位 9 种 = 72）+ 2 个 3（1 种）= 73

参考代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long a0 = 9, a1 = 1;  // 1 位数（含 0）

    for (int i = 2; i <= n; i++) {
        int b = (i == n) ? 8 : 9;  // 最高位不能是 0

        long long t0 = (a0 * b + a1) % 12345;
        long long t1 = (a1 * b + a0) % 12345;
        a0 = t0;
        a1 = t1;
    }

    if (n == 1) {
        cout << a0 - 1 << endl;  // 去掉开头的 0
    } else {
        cout << a0 << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，逐位递推
• 空间复杂度：O(1)