自动搬运

查看原文

来自洛谷，原作者为

	dbxxx 多刷题，少整那些没用的

搬运于2025-08-24 21:26:50，当前版本为作者最后更新于2019-01-16 00:05:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原来的题解因为叙说很云里雾里，代码过于追求简短而忽略可读性，现重写此篇题解。

我的思路是这样的：

首先对于给定的数的某一位，引入一个概念：贡献值。（自己创造的概念，并非官方）

设这一位所在位数为 $x$（从低位到高位数），上面的值为 $v$，那么这一位的贡献值：

• 如果 $v < 7$，那么这一位的贡献值为 $v \times 9^{x-1}$;
• 如果 $v > 7$，那么这一位的贡献值为 $(v - 1) \times 9^{x-1}$

做出了如上定义之后，一个不含 $7$ 的数字对应的答案就是每一位的贡献值之和。

接下来以 $n = 5482$ 为例（注意 $n$ 中不可含有 $7$，含有 $7$ 的情况稍后会处理），说明该算法是如何工作的。

首先我们运用位值原理，将 $5482$ 拆分为 $5000 + 400 + 80 + 2$

那么实际上，$1 \sim 5482$ 中所有 Pascal 数的总数，第一步就被我们拆分为：$0 \sim 4999$；$5000 \sim 5399$；$5400 \sim 5479$；$5480 \sim 5481$。

不知道到了这里你会不会萌生这样一个困惑：你是不是多算了一个 $0$ 呀？你是不是少算了一个 $5482$ 呀？

事实上，$0$ 是 Pascal 数，$5482$ 也是 Pascal 数，少算一个，多算一个，最后统计出的数据仍然是准确的。

解答你的疑惑后，我们继续再来分步处理这些部分：

$0 \sim 4999$ Pascal 数的数量是多少呢？第一个数可以从 $0$ 取到 $4$，总共有 $5$ 种情况；第二个数可以从 $0$ 取到 $9$，但不能是 $7$，总共有 $9$ 种情况；第三个数可以从 $0$ 取到 $9$，但不能是 $7$，总共有 $9$ 种情况；第四个数也是这样，$9$ 种情况。

考虑使用乘法原理：$5 \times 9 \times 9 \times 9$。这就是$0 \sim 4999$ Pascal 数的数量了。

那么，$5000 \sim 5399$ Pascal 数的数量是多少呢？第一个数只能取 $5$，不用考虑（或者考虑为 $1$ 种情况，最后乘法时不影响）；第二个数可以从 $0$ 取到 $3$，总共有 $4$ 种情况；第三个数 $9$ 种；第四个数 $9$ 种。

最后就是 $3 \times 9 \times 9$。

不知道你发没发现这样一个规律：分步考虑后，每一位（值为 $v$）对应区间内 Pascal 数的数量其实就是：$v$（从 $0$ 取到 $v - 1$ 共 $v$种情况），乘上后面位数数量的 $9$。也就应了刚刚那个贡献值的第一个式子。

现在你明白了吗？所谓贡献值其实就是每一位对应区间内 Pascal 数的数量。这个区间的映射关系，是通过拆分实现的。

到第三位开始情况有了变化：变化在于这一位上是 $8$，但这一位的取值范围不再是 $0 \sim 8$，因为 $7$ 也是需要扣去的！！

最后第一位就变成了 $v - 1$ 种情况，乘法原理时相应也需要是 $v - 1$ 与那么多 $9$ 相乘。应了刚刚贡献值的第二个式子。

第四位后面就没有位数了，所以直接就是 $v$，不用乘 $9$，也可以说是乘 $9^0$（ $=1$ ）。

最后把每一位的贡献值相加，自然就是最终结果啦。

什么？结束了吗？

不要忘了，数里边含有 $7$ 的情况，我们还需要拯救一下！

事实上，只需要在事前加这样一个小特判：从最高位往下扫，如果遇到 $7$，那么这一位变成 $6$，之后所有位都变成 $9$。

事实上道理也很简单，举个简单例子便可说明：$1 \sim 5700700$ 的所有 Pascal 数的数量其实和 $1 \sim 5699999$ 是一样的。毕竟，$5700000 \sim 5700700$ 的所有数都不是 Pascal 数。

代码：

#include <bits/stdc++.h>//万能头

int T;
std :: string s;
//这道题推荐字符串存储，因为要取的是每一位的值，且不涉及到整个数字的数字运算
int main() {
    std :: scanf("%d", &T);
    while (T--) { //多组数据测试时推荐这么写！
        std :: cin >> s;
        //特判开始
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '7') {
                s[i] = '6';//先把这一位标记为6
                for (int j = i + 1; j < s.length(); ++j)
                    s[j] = '9';//之后所有标记为9
                break; //跳出特判循环，这个 break 实际上很重要，不可省略
                //因为 700700 要变成 699999 而不是 699699
            }
        }
        //特判结束，正片开始
        int ans = 0; //初始化ans
        for (int i = s.length() - 1, atr = 1; i >= 0; --i, atr *= 9)
            ans += atr * (s[i] - '0') - (s[i] - '0' > 7 ? atr : 0);
            //重头戏！s[i] - '0' 就是 i 这一位代表的数字。
            //先根据贡献原理加贡献，然后再判断是否大于7
            //如果大于 7，那么扣除 atr，总体也就相当于 (s[i] - '0' - 1) * atr，合理
            //如果不大于 7，那么扣除 0，也就是不扣除。
        std :: printf("%d\n", ans); //输出答案
    }
    return 0;
}