信息奥赛题解｜位数问题
🚀 题目浏览
【题目描述】
在所有的 $N$ 位数中，有多少个数中有偶数个数字 $3$ ? 由于结果可能很大，你只需要输出这个答案对 $12345$ 取余的值。
【输入】
读入一个数 $N(N \le 1000)$。
【输出】
输出有多少个数中有偶数个数字 $3$。
【输入样例】
2【输出样例】
73【原题链接】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1313
☘️ 题解分析
本题对于 算法初学者 来说有点难度，且网络上的题解都不是特别清晰，故摊主撰写了本篇详细的题解分析，希望能在未来帮助到更多的同学。
首先以 $N=1$，即 一位数 为例，统计一位数中 包含偶数个 3 的个数，记作 $f[1]_偶$ ；统计包含奇数个 3 的个数，记作 $f[1]_奇$
- 由于 0 也是偶数，所以 「0 个 3」 也满足偶数个 3 的条件，故 $f[1]_偶$ 为 1～2，4～9，共 8 个数（注意：0 不是一位数），$f[1]_偶 = 8$
- 奇数个3 的情况只有单独的 3，所以 $f[1]_奇 = 1$
🍉 PS：有的小伙伴可能会问，题目不是求偶数的情况就够了吗？为什么要还要统计奇数的情况？继续往下看，你就明白了）
然后以 $N=2$，即 两位数 为例，统计两位数中 包含偶数个 3 的个数，记作 $f[2]_偶$ ；统计包含奇数个 3 的个数，记作 $f[2]_奇$
对于 $f[2]_偶$，可以分两种情况进行统计：
- 十位为 3，则 个位必须为奇数个 3，数量为 $f[1]_奇$
- 十位不为 3（十位可以为 1～2，4～9，共 8 个数），则 个位必须为偶数个 3 ，数量为 $f[1]_偶$
所以 $f[2]_偶 = f[1]_奇 + 8 * f[1]_偶$
然后我们带入 $f[1]_奇$、$f[1]_偶$ ，得 $f[2]_偶 = f[1]_奇 + 8 * f[1]_偶=1+8*8=65$ ，却发现与样例答案 73 不相等。❌
这是什么原因造成的呢 ? 🧐
实际上，当我们单独拿$f[1]_奇$、$f[1]_偶$ 讨论时，由于 0 不为一位数，所以 $f[1]_偶$ 为 1～2，4～9，共 8 个。
但是当 $N=2$ 时，由于十位上有了数字，所以此时个位上的数字是可以为 0 的，因此在计算 $f[2]_偶$ 时，$f[1]_偶$ 可以取到 0～2，4～9，共 9 个。（本质是 一位数 和 个位上的数字 的区别）
同理，$f[1]_奇$ 也要考虑 0 的情况，但是此时 0 并不满足 「奇数个3的条件」，所以 $f[1]_奇$ 仍然为 1（这里 $f[1]_奇$ 的值虽然没有变，但是后面的 $f[2]_奇、f[3]_奇$、…、$f[n]_奇$ 的值会在更新后发生改变）
把新的 $f[1]_偶$、$f[1]_奇$ 的值带入，得到 $f[2]_偶 = f[1]_奇 + 8 * f[1]_偶=1+8*9=73$
即为样例答案 73。
同理，$f[2]_奇 = f[1]_偶 + 8 * f[1]_奇=9+8*1=17$
上面这个 $f[1]_偶$、$f[1]_奇$ 为什么要更新的的原因，是本题的难点，也是本题的解题关键。现在不理解也没关系，继续往下阅读，再分析一个案例，也许你就理解了。
然后以 $N=3$，即 三位数 为例，也是类似的过程。
对于 $f[3]_偶$，可以分两种情况：
- 百位为 3，则 十位和个位总体 必须为 奇数个 3，数量为 $f[2]_奇$
- 百位不为 3，则 十位和个位总体 必须为 偶数个 3，数量为 $f[2]_偶$
所以 $f[3]_偶 = f[2]_奇 + 8 * f[2]_偶$
同理，$f[3]_奇 = f[2]_偶 + 8 * f[2]_奇$
同样，由于在计算 $f[2]_奇$ 、$f[2]_偶$ 时，十位不能为0；而引入百位后，十位可以为 0，所以如果要输出的是三位数的结果，则在计算 $f[2]_奇$ 、$f[2]_偶$ 时，也需要考虑 0
现在我们 重新计算 求解 $f[3]_偶$ 、$f[3]_奇$ 情况下的 $f[2]_偶$ 、$f[2]_奇$
我们在上一步中计算的 $f[2]_偶 = f[1]_奇 + 8 * f[1]_偶=1+8*9=73$
其中 8 这个系数，是十位不为 3 ，取 1～2，4～9 得到的（当时十位不能为 0）。但是现在，由于十位可以为0 ，所以十位可以取 0～2，4～9 共 9 个数字，所以上面式子中的系数应该为 9，而不是 8。
所以新的 $f[2]_偶 = f[1]_奇 + 9 * f[1]_偶=1+9*9=82$
同理，新的 $f[2]_奇 = f[1]_偶 + 9 * f[1]_奇=9+9*1=18$
在得到了新的 $f[2]_偶$、$f[2]_奇$ 后，再带入 $f[3]_偶 = f[2]_奇 + 8 * f[2]_偶$，就能得到正确的 $f[3]_偶$
🍉 PS：$f[3]_偶 = f[2]_奇 + 8 * f[2]_偶$，这里的系数 8 并不会变成 9，因为此时百位是最高位，不能为 0。
但是同理，当 $N=4$ 时，由于有千位的存在，百位就可以为 0 ，那么计算$f[3]_偶$ 时，其数值就应该更新为 $f[3]_偶 = f[2]_奇 + 9 * f[2]_偶$
上面推导过程中， $f[2]_偶$、$f[2]_奇$ 为什么要更新，并且 「公式系数从 8 改为 9」的原因，以及计算 $f[3]_偶$、$f[3]_奇$ 时，「公式系数仍为 8 」的原因，是本题的难点，也是本题的解题关键。⭐️
根据上面的推导，我们可以得到最终 n 位数的结果：
$f[n]_偶 = f[n-1]_奇 + 8 * f[n-1]_偶$
$f[n]_奇 = f[n-1]_偶 + 8 * f[n-1]_奇$
而在计算 $f[n-1]_奇$、$f[n-1]_偶$ 时，由于此时最高位可以为 0，上面递推式中表示 1～2，4～9的系数「8」就变成了0～2，4～9的系数「9」，递推公式为：
$f[n-1]_偶 = f[n-2]_奇 + 9 * f[n-2]_偶$
$f[n-1]_奇 = f[n-2]_偶 + 9 * f[n-2]_奇$
所以在书写代码时，也需要分为两个表达式来写。✅
🍉 PS1：在实际编程中，我们可以用 $f[N][0]$ 来表示 $f[N]_偶$ ，用 $f[N][1]$ 来表示 $f[N]_奇$
🍉 PS2：这种递推问题的答案可能很大，甚至超出 long long 的范围，所以不要忘记题干中的取模要求。
🧑🏻💻 C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int K = 12345;
int n;
int f[N][2]; //f[n][0]表示 n位数 中包含偶数个3的情况
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
cin >> n;
if (n == 1) {
f[1][0] = 8; //1~2,4~9 共 8 个
f[1][1] = 1; //3，共1个
cout << f[1][0] << endl;
} else {
f[1][0] = 9; //更高位上有数字，需要考虑0
f[1][1] = 1;
//递推2～n-1位数
for (int i = 2; i <= n - 1; ++i) {
//K = 12345
f[i][0] = ((f[i - 1][1] % K) + (9 * (f[i-1][0] % K)) % K) % K;
f[i][1] = ((f[i - 1][0] % K) + (9 * (f[i-1][1] % K)) % K) % K;
}
//单独计算n位数
f[n][0] = ((f[n - 1][1] % K) + (8 * (f[n-1][0] % K)) % K) % K;
cout << f[n][0] << endl;
}
return 0;
}😑 吐槽时间
摊主本人在阅读其他一些题解时，发现有的题解在分析时，认为 $f[1][0]=8$（ 1～2，4～9，因为 0 不算一位数），但是实际代码中，却出现 $f[1][0] = 9$ 的情况，并且没有交代原因。这样的前后矛盾，让不少看题解的小伙伴们感到困惑。
摊主还发现，有的题解就直接认为 $f[1][0]$ 就应该等于 9，把 0 也算成了一位数，这从 数学定义的角度 来看是错误的。❌ （有疑惑的小伙伴可以查阅以下问题：0 算不算一位数 ? 一位数和个位数有什么区别？）
从推导过程中，我们看到只有在 $N > 1$ 时，f[1][0] 才因为进制的规则，变成了 9。
说明写其他题解的作者可能没有仔细考虑这其中的关系，这也是摊主撰写此篇题解的原因，希望本题解能真正解答一些小伙伴们的困难。
摊主也希望阅读此篇题解后，理解了本题的小伙伴，在未来自己写其他题目的题解时，多一份耐心与细致，不要让更多灌水、没有太多思考的题解，污染了这片土壤，浪费其他小伙伴搜索与阅读的时间。☘️
