题目链接：https://www.luogu.com.cn/problem/P1980
术语
以下的英文术语均可以翻译为数字。
digit: 一个数字字符，十进制就是 0-9 之间的一个字符；
numeral: 用来表示数字的符号化表示，如 “Three”、“3”、“III”；
number: 一种抽象的数字概念。
为了区分，下文中均使用英文术语。
注意：关于 numeral 和 number 区别见: 如何在英文写作中正确的表达数字？
十进制数表示法
十进制数(decimal numeral)由一串有限长度的 digit 序列组成，
\[a_ma_{m-1}\ldots a_0
\]
其中，\(a_i \in \{0,1,2,3,4,5,6,7,8,9\}\)。
numeral \(a_ma_{m-1}\ldots a_0\) 表示了 number \(a_m10^m+a_{m-1}10^{m-1}+\cdots+a_{0}10^0\)。
注意：关于十进制数的详细介绍见 Wikipedia Decimal
前置 \(0\)
为简化问题，我们假设我们的 numeral 可以出现前置 \(0\)，即，从最左侧开始，可以出现多个连续的 \(0\)，如 \(03\)，\(003\)。通过前置 \(0\)， 我们可以使用三个 digit 来包含一位数、二位数、三位数的 number。
三个 digit
为简化问题，我们目前只考虑三位数之内的 number，且忽略 \(n\)（目前可视作 \(n = 999\)，用来包含所有的一位数、二位数、三位数)。
出现次数是？
根据题目，我们需要统计出 digit \(x\) 在所有 numeral 的 digit 中出现的次数。这里我们列出部分的 numeral，
\[\begin{array}
{c|c|c}
a_2&a_1&a_0\\
\hline
0&0&0\\
0&0&1\\
0&0&2\\
0&0&3\\
\vdots&\vdots&\vdots\\
9&9&6\\
9&9&7\\
9&9&8\\
9&9&9\\
\end{array}
\]
令 \(C_i\) 等于第 \(i\) 位上 \(x\) 出现的总次数，那么\(x\) 在所有 numeral 的 digit 中出现的次数为 \(S=\sum_{i=0}^2C_i\)。
\(C_i\) 等于？
我们通过 \(x = 1\) 来进行说明。首先我们令 \(a_2 = 1\)，此时百位上的数字已经固定，\(a_1\) 和 \(a_0\) 分别有 \(0\) 到 \(9\) 十种可能，且彼此互不影响，所以 \(C_2 = 10 \times 10 = 100\)，同理我们得到 \(C_0=C_1=100\)。从而，我们最终得到 \(S=100+100+100=300\)。
通过上面的方式，我们可以得到任意 \(x\) 对应的 \(S\)。
注意：
digit\(0\) 比较特殊，我们这里暂时未考虑。
考虑 \(n\) 呢？
上面的问题只看 digit 的个数，但忽略了 \(n\)。如果我们也要将 \(n\) 考虑在内呢？
\(n=123\), \(x=3\)
这里以 \(n=123\)，\(x=3\) 进行举例。首先我们可以知道 \(a_2 = 3\) 是不可能的，所以此时 \(C_2 = 0\)。下面我们考虑 \(a_1 = 3\)，此时 \(a_2\) 必须小于 \(1\), 所以只有 \(a_2 = 0\) 一种可能，由于向前面借了一位， \(a_0\) 可以包含 \(0\) 到 \(9\) 十种可能，从而我们得到 \(C_1 = 10\)。然后我们考虑 \(a_0 = 3\)，当 \(a_2 = 1\) 时，需满足 \(a_1 \leqslant 2\)；当 \(a_2 = 0\) 时，\(a_1\) 可以包含 \(0\) 到 \(9\) 十种可能，加起来我们有 \(C_0 = 3 + 10 = 13\) 种可能。最终，我们得到 \(S=0+10+13=23\)。
\(n=123\), \(x=2\)
这里以 \(n=123\)，\(x=2\) 进行举例。首先我们可以知道 \(a_2 = 2\) 是不可能的，所以此时 \(C_2 = 0\)。下面我们考虑 \(a_1 = 2\)，此时 \(a_2\) 有 \(0\) 和 \(1\) 两种可能，当 \(a_2 = 1\), 需满足 \(a_1 \leqslant 3\)；当 \(a_2 = 0\), \(a_1\) 可以包含 \(0\) 到 \(9\) 十种可能，从而我们得到 \(C_1 = 4 + 10 = 14\)。然后我们考虑 \(a_0 = 2\)，当 \(a_2 = 1\) 时，需满足 \(a_1 \leqslant 2\)；当 \(a_2 = 0\) 时，\(a_1\) 可以包含 \(0\) 到 \(9\) 十种可能，加起来我们有 \(C_0 = 3 + 10 = 13\) 种可能。最终，我们得到 \(S=0+14+13=27\)。
\(n=123\), \(x=1\)
这里以 \(n=123\)，\(x=1\) 进行举例。首先我们令 \(a_2=1\)，当 \(a_1=2\) 时，需满足 \(a_0 \leqslant 3\)；当 \(a_1 \leqslant 1\) 时，\(a_0\) 可以包含 \(0\) 到 \(9\) 十种可能，故 \(C_2 = 4 + 10 + 10 = 24\)。下面我们考虑 \(a_1 = 1\)，此时 \(a_2\) 有 \(0\) 和 \(1\) 两种可能，当 \(a_2 \leqslant 1\), \(a_0\) 可以包含 \(0\) 到 \(9\) 十种可能，从而我们得到 \(C_1 = 10 + 10 = 20\)。然后我们考虑 \(a_0 = 1\)，当 \(a_2 = 1\) 时，需满足 \(a_1 \leqslant 2\)；当 \(a_2 = 0\) 时，\(a_1\) 可以包含 \(0\) 到 \(9\) 十种可能，加起来我们有 \(C_0 = 3 + 10 = 13\) 种可能。最终，我们得到 \(S=24+20+13=57\)。
我们发现上面的统计方式，通过程序来处理的话比较麻烦，最好一种统一的方式来处理各种情况，
移除 digit \(x\)，再看看！
\(x > a_i\)，
当 \(x > a_i\)，我们令 \(a_{i-1} \gets a_{i-1} - 1\)，\(a_k \gets 9 \text{ for } k > i\)。比如对于 \(n = 123\), \(x=3\)，\(i = 2\)，我们得到 \(039\)，我们移除 \(a_2\) 得到 \(09\)，在对 \(09 + 1\) 得到 \(10\)，我们发现这正好等于 \(C_2\)；
\(x = a_i\)，
当 \(x = a_i\)，不进行额外操作。比如对于 \(n = 123\), \(x=2\)，\(i = 2\)，我们得到 \(123\)，我们移除 \(a_2\) 得到 \(13\)，在对 \(13 + 1\) 得到 \(14\)，我们发现这也正好等于 \(C_2\)；
\(x < a_i\)，
当 \(x = a_i\)，我们令 \(a_k \gets 9 \text{ for } k > i\)。比如对于 \(n = 123\), \(x=1\)，\(i = 2\)，我们得到 \(119\)，我们移除 \(a_2\) 得到 \(19\)，在对 \(19 + 1\) 得到 \(20\)，我们发现这又正好等于 \(C_2\)。
上面的方法可以总结为，
- 首先判断 \(x\) 和 \(a_i\) 的大小关系；
根据判断结果来对其他的
digit 进行修改；移除 \(x\) 对应的 \(a_i\)，得到一个新的
numeral计算
numeral 对应的 number最后在对得到的结果 \(+1\) 即可。
注意：如果 \(a_i\) 最高位，且 \(x > a_i\)，那么此时没有可以借位的
digit，所以 \(C_i = 0\)。
注意：
digit\(0\) 比较特殊，我们这里暂时未考虑。
多出来 \(0\)？
如果我们按照前面的方法对 \(x = 0\) 进行统计，我们会发现 \(0\) 的次数被多统计了一些。
为了解释这个问题，这里我们再次以三个 digit 的 numeral 进行说明。
对于任意一个三位数的 \(n\)，我们之前的方法会把所有有一个前置 \(0\) 和有两个前置 \(0\) 的 numeral 包含进来，比如 \(010\)，\(001\)。而这些前置 \(0\) 实际上不应该被统计进来，为了得到正确的答案，我们可以在最终结果的地方减去多统计的前置 \(0\) 。
前置 \(0\) 的个数
前置 \(0\) 的个数为 \(a_2 = 0\) 的 numeral 个数，以及 \(a_2=0\) 同时 \(a_1 = 0\) 的numeral 个数，因为题目中 number 不包含 \(0\)，所以我们最终还要加上 \(a_2=0\) 同时 \(a_1 = 0\) 同时 \(a_0 = 0\) 的情况。最终我们可以得到多统计的前置 \(0\) 个数为 \(100 + 10 + 1 = 10^2 + 10^1 + 10^0 = 111\)。
由此我们可以推广 \(m\) 个 digit 的 numeral 多统计的前置 \(0\) 为 \(\sum_{i=0}^{m-1} 10^i\)。
结论
\(x \ne 0\) 时，采用移除 digit \(x\) 的方法即可。
\(x = 0\) 时，采用移除 digit \(x\) 方法的同时还需要减去多余的前置 \(0\)。
代码如下：
// https://www.luogu.com.cn/problem/P1980
// https://www.cnblogs.com/revc/p/17087297.html
#include <iostream>
#include <cmath>
int main()
{
int n, x;
std::cin >> n >> x;
int digits[7];
int m = 0; // the number of digits
while(n > 0) // NOTE: store digits in reverse order
{
digits[m++] = n % 10;
n /= 10;
}
int S = 0;
for (int i = 0; i < m; i++)
{
int C = 0;
int borrow = 0;
if (x > digits[i])
{
if (i+1 == m) continue; /* fail to borrow */
borrow = 1;
digits[i+1]--;
}
for (int j = m - 1; j > i; j--)
{
C = C * 10 + digits[j];
}
for (int j = i - 1; j >= 0; j--)
{
C = C * 10 + (digits[i]==x ? digits[j] : 9);
}
digits[i+1] += borrow;
S += C + 1;
}
if (x == 0)
{
int subtrahend = 1;
while(m--)
{
S -= subtrahend;
subtrahend *= 10;
}
}
std::cout << S << std::endl;
return 0;
}
