2025年一本通题解——1313：【例3.5】位数问题

大家好，我是讯享网，很高兴认识大家。

题目相关

题目链接

一本通 OJ，http://ybt.ssoier.cn:8088/problem_show.php?pid=1313。

题目描述

在所有的 N 位数中，有多少个数中有偶数个数字 3？由于结果可能很大，你只需要输出这个答案对 12345 取余的值。

输入

读入一个数 N (N ≤ 1000)。

输出

输出有多少个数中有偶数个数字 3。

样例输入

讯享网

样例输出

讯享网73

题目分析

题意

找出所有 N 位数中，包含偶数个 3 的数字个数。

样例数据分析

样例输入 2，表示所有 2 位数，那就是 10 ~ 99，一共有 99-10+1=90 个数字。由于数据比较小，我们可以列出所有含有奇数个 3 的数字，即 13、23、30、31、32、34、35、36、37、38、39、43、53、63、73、83、93，这样合计 17 个数字。因此含有偶数个 3 的数字有 90-17=73 个。注意零也是偶数。

递推思路

当 N=1，数字范围为 0 ~ 9，合计 9-0+1=10 个。

（1）含有偶数个 3 数字有 9 个（0、1、2、4、5、6、7、8、9）。

（2）含有奇数个 3 数字有 1 个（3）。

讯享网

当 N=2，数字范围为 10 ~ 99，合计 99-10+1=90 个。

（1）含有偶数个 3 数字的构成：前面一位数中含有奇数个 3 数字，在其前面加上数字 3 的组合，有 1*1=1个，即数字 33，这样有 1 个数字；前面一位含有偶数个 3 数字（0、1、2、4、5、6、7、8、9），在其前面加上不是 3 的数字（1、2、4、5、6、7、8、9）的组合，有 8*9=72 个。合计 72+1=73。

（2）含有奇数个 3 数字的构成：前面一位数中含有奇数个 3 ，在其前面加上数字为（1、2、4、5、6、7、8、9）的组合，有 8*1=8 个。前面一位数中含有含有偶数个 3 数字（0、1、2、4、5、6、7、8、9），在其前面加上数字为 3 的组合，有 9*1=9 个。合计 8+9=17 个。

当 N=3，数字范围为 100 ~ 999，合计 999-100+1=900 个。

（1）含有偶数个 3 数字的构成：前面两位数字中含有奇数个 3（有 1*9+9*1 个，即18个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字），在其前面加上数字 3 的组合，合计 18*1=18 个；前面两位数字中含有偶数个 3（有 9*9+1*1 个，即82个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字），数字前加上不是 3 的数字（1、2、4、5、6、7、8、9），有 82*8=656。合计有 18+656=674 个。

（2）含有奇数个 3 数字的构成：前面两位数字中含有奇数个 3（有 1*9+9*1 个，即18个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字），在其前面加上不是 3 的数字（1、2、4、5、6、7、8、9）的组合，合计 18*8=144 个；前面两位数字中含有偶数个 3（有 9*9+1*1 个，即82个，注意这个时候数字 0 可以放在前头，因为百位我们还能加数字），数字前加上数字 3，有 82*1=82。合计有 144+82=226 个。

以此类推。这样我们就可以推倒出如下的递推公式：

N 表示位数，a[i] 表示到第 i 位包含偶数个 3 的数字数量，b[i] 表示到第 i 位包含奇数个 3 的数字数量 a[1] = 9 b[1] = 1 当 i<N 的时候 a[i] = a[i-1]*9 + b[i-1]*1 b[i] = a[i-1]*1 + b[i-1]*9 当 i==N 的时候，由于首位不能为零 a[i] = a[i-1]*8 + b[i-1]*1 b[i] = a[i-1]*1 + b[i-1]*8

AC 参考代码

讯享网#include <iostream> using namespace std; const int MAXN = 1e3+2; unsigned long long a[MAXN];//偶数个3 unsigned long long b[MAXN];//奇数个3 int main(){ int N; cin >> N; int K = 9; a[1] = 9; b[1] = 1; for (int i=2; i<=N; i++){ if (i==N) { K=8; } a[i] = (a[i-1]*K + b[i-1])%12345; b[i] = (a[i-1] + b[i-1]*K)%12345; } cout << a[N] << endl; return 0; }