【题解】位数问题
【题目描述】
在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。
比如：在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个。（请注意：1位数指1~9这9个数，不包含数字0）
【输入描述】
一个整数N（1<=N<=1000）
【输出描述】
N位数中含有偶数个数组3的个数
【样例输入】
2
【样例输出】
73
【分析】
初学时把数字写出来，然后找规律（递推找规律和公式）。
有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 位新数字”
加的这个新数字只有两种可能：不是 3 或 是 3，这两种情况会影响 “总 3 的个数的奇偶性”。
辅助初始条件：k=0（空数，0 个 3）时，f'(0)=1，g'(0)=0
情况 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 的情况
- 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
- 计算 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 的情况
- 先算 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
- 计算 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 的情况
- 先算 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
- 计算 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 的情况
- 先算 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
- 计算 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：归纳通用公式
- 观察 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)
- 联立两个方程
方程 1：f (N) + g (N) = 9×10^(N-1)
方程 2：f (N) - g (N) = 7×8^(N-1)
- 两式相加消去 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; }