【题目描述】

在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。
比如：在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个。（请注意：1位数指1~9这9个数，不包含数字0）

【输入描述】

一个整数N（1<=N<=1000）

【输出描述】

N位数中含有偶数个数组3的个数

【样例输入】

2

【样例输出】

73

【分析】

1. 初学时把数字写出来，然后找规律（递推找规律和公式）。

2. 有DP经验的使用DP思路求解。

【过程推导】

--------------------------------------------------

前提约定

N≥2 时是 10^(N-1) ~ 10^N - 1（共 9×10^(N-1) 个）

• f (N)：N 位数中含偶数个 3 的数量（目标值）

• g (N)：N 位数中含奇数个 3 的数量

• 总数关系：f (N) + g (N) = 9×10^(N-1)

• 辅助符号（
• k 位任意数：含前导 0，即 0~10^k - 1，共 10^k 个）

• f'(k)：k 位任意数中含偶数个 3 的数量

• g'(k)：k 位任意数中含奇数个 3 的数量

• 
  

• 辅助总数关系：f'(k) + g'(k) = 10^k

• 
  

• 辅助递推式：

  f'(k) = 9×f'(k-1) + 1×g'(k-1)   

  g'(k) = 9×g'(k-1) + 1×f'(k-1)

公式解释：

• f'(k)：k 位任意数（每一位可以是 0~9，比如 k=2 就是 00 到 99）中，包含偶数个 3的数的总个数；

• f'(k-1)：k-1 位任意数中，包含偶数个 3的数的个数；

• g'(k-1)：k-1 位任意数中，包含奇数个 3的数的个数；

核心逻辑：“k 位数 = k-1 位数 + 最后 1 位新数字”

情况 1：新数字不是 3（共 9 种选择：0、1、2、4~9）

• 新数字没贡献 3 → 原来 k-1 位数的 “3 的奇偶性”保持不变；

• 如果原来 k-1 位数有偶数个 3，加上这个新数字后，还是偶数个 3；

• 这种情况的数量 = 9 × f'(k-1)。

• 
  

情况 2：新数字是 3（共 1 种选择：只有数字 3）

• 新数字贡献了 1 个 3 → 原来 k-1 位数的 “3 的奇偶性”反转；

• 如果原来 k-1 位数有奇数个 3，加上这个新数字后，就变成偶数个 3；

• 这种情况的数量 = 1 × g'(k-1)。

步骤 1：计算 N=1 的情况

1. N=1（1~9）

• 偶数个 3：0 个 3（1、2、4-9）→ 数量 = 8 → f (1)=8

• 奇数个 3：1 个 3（仅数字 3）→ 数量 = 1 → g (1)=1

• 验证总数：8+1=9=9×10^0 

2. 计算 1 位任意数（0~9）

• f'(1)=9×f'(0)+1×g'(0)=9×1+1×0=9

• g'(1)=9×g'(0)+1×f'(0)=9×0+1×1=1

• 验证总数：9+1=10=10^1 

• 
  

步骤 2：计算 N=2 的情况

1. 先算 2 位任意数的辅助值（k=2）

• f'(2)=9×f'(1)+1×g'(1)=9×9+1×1=82

• g'(2)=9×g'(1)+1×f'(1)=9×1+1×9=18

• 验证总数：82+18=100=10^2 

2. 计算 N=2（10~99）

• f(2)=8×f'(1)+1×g'(1)=8×9+1×1=72+1=73

• g (2)= 总数 - f (2)=9×10^(2-1) -73=90-73=17

• 验证总数：73+17=90 

• 
  

步骤 3：计算 N=3 的情况

1. 先算 3 位任意数的辅助值（k=3）

• f'(3)=9×f'(2)+1×g'(2)=9×82+1×18=738+18=756

• g'(3)=9×g'(2)+1×f'(2)=9×18+1×82=162+82=244

• 验证总数：756+244=1000=10^3 

2. 计算 N=3（100~999）

• f(3)=8×f'(2)+1×g'(2)=8×82+1×18=656+18=674

• g (3)= 总数 - f (3)=9×10^(3-1)-674=900-674=226

• 验证总数：674+226=900 

• 
  

步骤 4：计算 N=4 的情况

1. 先算 4 位任意数的辅助值（k=4）

• f'(4)=9×f'(3)+1×g'(3)=9×756+1×244=6804+244=7048

• g'(4)=9×g'(3)+1×f'(3)=9×244+1×756=2196+756=2952

• 验证总数：7048+2952=10000=10^4 

2. 计算 N=4（1000~9999）

• f(4)=8×f'(3)+1×g'(3)=8×756+1×244=6048+244=6292

• g (4)= 总数 - f (4)=9×10^(4-1)-6292=9000-6292=2708

• 验证总数：6292+2708=9000 

• 
  

步骤 5：归纳通用公式

1. 观察 f (N) 和 g (N) 的差值

• N=1：f(1)-g(1)=8-1=7=7×8^0

• N=2：f(2)-g(2)=73-17=56=7×8^1

• N=3：f(3)-g(3)=674-226=448=7×8^2

• N=4：f(4)-g(4)=6292-2708=3584=7×8^3

• 规律：f (N) - g (N) = 7×8^(N-1)

2. 联立两个方程

• 方程 1：f (N) + g (N) = 9×10^(N-1)

• 方程 2：f (N) - g (N) = 7×8^(N-1)

3. 两式相加消去 g (N)

• [f(N)+g(N)] + [f(N)-g(N)] = 9×10^(N-1) +7×8^(N-1)

• 2×f(N) = 9×10^(N-1) +7×8^(N-1)

• 最终公式：f (N) = [9×10^(N-1) +7×8^(N-1)] / 2

参考答案

#include <iostream>
using namespace std;
// 快速幂
long long kuaisu(long long a, long long b, long long mod) {
    long long result=1;
    // 先把底数取模，防止初始值过大
    a=a%mod;
    while (b>0) {
        // 如果指数是奇数，结果先乘上当前底数
        if (b%2==1) {
            result=(result*a)%mod;
        }
        // 指数折半，底数平方
        a=(a*a)%mod;
        b=b/2;
    }
    return result;
}

int main() {
    int N;
    cin >> N;
    // 因为公式要除以2，先对mod*2取模，避免除法出错
    long long mod = 12345*2;
    // 计算第一项：9 * 10^(N-1)
    long long term1 = (9*kuaisu(10, N-1, mod)) % mod;
    // 计算第二项：7 * 8^(N-1)
    long long term2 = (7*kuaisu(8, N-1, mod)) % mod;
    // 两项相加后取模
    long long sum = (term1 + term2) % mod;
    // 除以2后再对12345取模，得到最终结果
    int answer=(sum/2) % 12345;
    cout << answer << endl;
    return 0;
}