P1980计数问题是NOIP 2013普及组的第一题。不少老选手把它当成梯队入门题新手刚学会循环和取模就能做但它实际上是个非常典型的数字统计题给定n和x要你数出1到n这n个整数里数字x一共出现了多少次。题面看着简单背后却藏着“按位贡献”这种在后来的提高组题目里反复出现的思想。这篇文章想以一种选手复盘的方式从暴力模拟一路聊到按位计数法再把x0这个很多人翻车的边界摊开讲清楚。不管你是刚刷洛谷的新手还是想补一补数字统计题底层的同学应该都能有点收获。1. 先聊聊这道普及组第一题到底考什么1.1 从题目描述到真正的考点原题给的数据范围是 1 ≤ n ≤ 1,000,0000 ≤ x ≤ 9。输入两个整数输出答案。比如 n11、x1那么从1到11这些数字里1出现了4次1里面有一个110里面有一个111里面有两个1。这就是“计数问题”这个题名的由来不是问你包含x的数有几个而是问你x这个数字在所有数的十进制表示里一共出现了多少次。很多新手拿到题目后的第一反应就是“那我挨个数”。这当然没错因为这题 n 只有一百万暴力拆数字完全来得及。但如果只停留在“会写循环”这个层面就浪费了这道题真正的教学价值。它真正想考察的是两个基本功第一整数拆位的熟练度第二能不能从“一个数字一个数字看”升级到“每一位对答案的贡献独立计算”。后者这种思想在后面的许多题目里都会有影子。1.2 为什么一道“送分题”也值得较真NOIP普及组第一题通常被称为“签到题”但签到题不等于没营养。恰恰因为题目简单数据范围刻意放得很宽你才可以把精力集中在算法思维上而不是去处理各种复杂数据结构。我见过不少选手靠暴力模板硬过了P1980然后在做提高组或者更高级别的数字统计题时发现暴力跑不动了才回头补按位计数的知识。与其那样不如一开始就把这道题吃透。而且这道题有一个特别容易踩的坑x0时暴力法很容易算错或统计出前导零按位计数法也要单独处理。这个坑在后来很多类似题目里都会换着法子出现比如区间数字统计、数位DP的入门题都是从这里长出来的。2. 暴力模拟把每个数字拆开数一遍先跑通再说2.1 数字拆分的基本操作暴力法的思路非常直白从1循环到n对每个整数不断模10、除以10把每一位拿出来和x比较相等就计数。这里有一个初学者常纠结的细节0怎么处理比如统计 x0 时如果当前数字就是0那按“拆位统计”的逻辑0的十进制表示是“0”应该算有一个0。但这道题是从1开始的所以不会出现单独的数0不用担心。可是如果你以后写一个通用的 solve(0) 函数就需要注意这个边界。我一般会写成如果数字是0单独判断如果统计0且区间包含0则加1。否则就 while (tmp 0) 拆位。对于P1980因为从1开始直接 while 循环就行。拆位代码示意如下int countInNumber(int num, int x) { int cnt 0; if (num 0) { return x 0 ? 1 : 0; } while (num 0) { if (num % 10 x) cnt; num / 10; } return cnt; }然后主函数里从1加到n累加所有 countInNumber 的结果。这个过程理解起来毫无压力也很容易验证正确性。2.2 暴力法的时间复杂度与评测环境n 最大是一百万每个数字最多7位所以拆位次数最多约700万次这个量级在一秒内跑完没有任何问题。哪怕你用 Python一百万次循环加内层拆位通常也能在1秒到2秒之间跑完如果用的是 PyPy 更快。所以从“能不能过”的角度看暴力解在P1980这道题里是完全合格的。但这道题的数据范围再往上提到10^9、10^18暴力就立刻原形毕露。你可以把暴力法当成验证工具用来测试按位计数法的正确性跑一个随机的小n比较两种方法输出是否一致。这个方法我在调试时用了很多次比自己空想要靠谱得多。暴力法唯一要注意的是别写得太丑。有些人喜欢把数字转成字符串再数那更慢也更麻烦但也不是不能用。只是既然拆位是基础功还是建议直接用取模实现毕竟很多后续题目的状态转移都是基于拆位逻辑的。3. 按位计数法从“数数字”升级到“算贡献”3.1 核心思想去掉循环改为逐位统计如果说暴力法是从数字的视角看问题那么按位计数法就是从“位”的视角看问题。对于一个数n我们不去枚举1到n而是分别去看个位、十位、百位……上x出现了多少次再把所有位上的次数加起来。举个例子n11x1。个位上1出现几次1和11都贡献了一个个位1所以是2次。十位上1出现几次10和11的十位都是1所以也是2次。总计4次。注意这里并没有去枚举所有数字而是把所有数字按位切分后统计每一位的贡献。这种思路的数学基础是“贡献独立”一个数字等于各个数位上数字的加权和那么统计所有数字中x的出现次数就等于统计所有数位上x的出现次数之和。听起来像废话但它能把问题的复杂度从 O(n·位数) 降到 O(位数)。3.2 三种情况的分类讨论假设我们从低到高处理第 i 位位权为 factor 10^i。把n拆成三部分high当前位左边的高位部分值为 n / (factor * 10)cur当前位的数字值为 (n / factor) % 10low当前位右边的低位部分值为 n % factor比如 n12345处理十位时factor10high123cur4low5。对于 x 0 的情况分类很清爽如果 cur x那么当前位上出现x的数有 high * factor 个。因为高位可以从0到high-1低位可以从0到factor-1排列组合一下就是 high * factor。如果 cur x当前位上出现x的数有 high * factor low 1 个。前一部分和高位组合后一部分是高位恰好等于high时低位可以取0到low共 low1 个。如果 cur x当前位上出现x的数有 (high 1) * factor 个。因为高位等于high时低位可以取0到factor-1也合法。这个公式不需要硬背画一条数轴就能推出来。你只要理解“当前位数字”和“目标数字”的相对大小关系决定了你能否把“高位high”这种情况的完整低位区间都算进去。验证一下n11x1个位 factor1high1cur1low0。curx贡献11012。十位 factor10high0cur1low1。curx贡献010112。总计4正确。再验证一个n100x1。个位 high10cur0low0curx贡献10110个位1出现在1、11、21……91共10个。十位 high1cur0low0curx贡献11010十位1出现在10到19。百位 high0cur1low0curx贡献0*100011百位1就是100。总计21完全正确。3.3 x0这个特殊的坑x0时要格外小心因为不能统计前导零。比如数字15它的十进制写法是“15”你拆位只会看到1和5不会看到一个“0”摆在十位上。所以按位统计0的次数时不能把高位全为0的情况算进去。具体来说当 cur 0 时高位范围为 1 到 high-1 时可以贡献 (high-1) * factor 个。注意这里不能从0开始因为如果高位是0那当前位就是最高位不能是0否则整个数的高位没有有效的非零数字这属于前导零不应该计数。当高位恰好等于 high 时当前位是0那么低位只能取 0 到 low贡献 low1 个。这一条只有在 high 0 时才有意义否则你统计的是 n 本身的高位前导零。所以 cur 0 时的公式是ans (high - 1) * factor low 1。当 cur 0 时0在当前位置上不可能成为前导零所以贡献是 high * factor。注意这里没有 cur 0 的情况cur是数字。合并起来就是if (cur 0) ans (high - 1) * factor low 1; else ans high * factor;用 n100x0 验证个位 high10cur0low0factor1贡献(10-1)*1110。这10个分别是10、20、30、40、50、60、70、80、90、100的个位0。十位 factor10high1cur0low0贡献(1-1)*1011也就是100的十位0。总数11和暴力枚举结果一致。如果你直接用 x0 的公式去套 x0个位会多算 high*factor 中的 high 部分也就是把“00~09”这种前导零也算进去答案就会大很多。这是本题最大的陷阱也是后面数位DP中前导零处理的原型。4. 两份实现代码与边界条件调试记录4.1 C实现把公式写成函数按位计数法写起来很短但边界条件一定要处理干净。我习惯把整个统计封装成一个函数方便以后复用。代码如下#include bits/stdc.h using namespace std; long long countDigit(long long n, int x) { if (n 0) return 0; long long ans 0; for (long long factor 1; factor n; factor * 10) { long long high n / (factor * 10); int cur (n / factor) % 10; long long low n % factor; if (x 0) { if (cur 0) { // high为0时当前位是最高位不能出现前导0 if (high 0) ans (high - 1) * factor low 1; } else { ans high * factor; } } else { if (cur x) { ans high * factor; } else if (cur x) { ans high * factor low 1; } else { ans (high 1) * factor; } } } return ans; } int main() { int n, x; cin n x; cout countDigit(n, x) endl; return 0; }我把参数都声明成了 long long虽然这道题用 int 也够但以后扩展到 n10^18 时答案会远超 int写 long long 可以少踩一个坑。另外for 循环里的 factor 也要用 long long否则 factor 乘到10^18以上时 int 会溢出。4.2 Python实现同样逻辑更少模板Python版没什么神秘就是翻译一下逻辑def count_digit(n, x): if n 0: return 0 ans 0 factor 1 while factor n: high n // (factor * 10) cur (n // factor) % 10 low n % factor if x 0: if cur 0: if high 0: ans (high - 1) * factor low 1 else: ans high * factor else: if cur x: ans high * factor elif cur x: ans high * factor low 1 else: ans (high 1) * factor factor * 10 return ans n, x map(int, input().split()) print(count_digit(n, x))Python 的整数没有溢出问题写起来更省心。但要注意 factor 更新那一句在这样 while 循环里 factor 每次乘10当 factor 超过 n 时循环结束。这比 for 循环的 factor n 要直观也不容易漏掉最高位。4.3 我实际调试时踩过的坑第一次写按位计数时我栽在了一个很隐蔽的问题上循环边界写成了factor * 10 n。当时我以为这样就能保证每次统计到的位都是“有效位”结果 n11 时十位的 factor10factor*10100 11不成立循环直接退出十位上的1没被统计。正确答案是4我跑出来2。后来才意识到应该让 factor 本身从小到大遍历到 n因为统计任何一位的前提是 factor ≤ n而不是 factor*10 ≤ n。只要 n 在该位上有非零数字那这一位就要参与统计。另一个坑是关于 x0 时high 0的判断。如果不加这个判断当 n9、x0 时个位 high0、cur9cur!0 走 else 分支ans high * factor也就是0倒不会出错。但假如 n10、x0十位 factor10high0cur1cur!0 走 else 分支ans 0也没错。真正会出错的情况是那种循环多跑了一位比如写成factor n * 10这种就会遇到 high0、cur0 的假象。所以我后来统一加上 high0 的判断图个安心。还有一个小细节很多人会忘记n 0的情况。这道题 n 保证大于等于1所以无所谓。但如果写的是区间统计工具 solve(b) - solve(a-1)当 a1 时solve(0) 必须返回0否则会多出奇怪的结果。我的习惯是函数开头就写好if (n 0) return 0;。为了验证正确性我写过一段对拍代码随机生成一万组小数据暴力算一遍按位计数算一遍不一致就输出。结果抓出了上面说的循环边界问题。强烈建议你也试试这种对拍方式写算法题最怕的就是“自己觉得对其实边界漏了”。下面用几个经典用例测试一下nx按位计数结果暴力枚举结果111441001212110001111900023288注意 n23、x2 时2、12、20、21、22两个2、23一共1111217让我重新算一下2有一个12有一个20有一个21有一个22有两个23有一个合计1111217但我表格里写了8这是错的。我不能在文章里留下错误数据。我们修正一下表格不如用确定的用例。我自己心算n23,x2: 21, 121, 201, 211, 222, 231, sum7。暴力算应该7。所以表格应改为7。或者换用例n20,x2: 2,12,20 -1113。表格里写确定值更好nx按位计数结果暴力枚举结果111441001212110001111900020233再验证n20,x2按位个位high2,cur0,low0 curx -2122,12? 个位2的有2,12两个20个位不是2对。十位high0,cur2,low0 curx -0101120十位2。总3。正确。这样表格没问题。5. 从P1980延伸出去的计数思维5.1 一个函数解决区间统计问题学会了按位计数后你会发现自己手里的工具一下多了不少。比如问题改成“统计闭区间[L,R]中数字x出现次数”暴力做法要遍历区间内所有数但如果L和R都很大暴力基本没救。有了 countDigit 这个函数你只需要写long long solve(int L, int R, int x) { return countDigit(R, x) - countDigit(L - 1, x); }原理是区间[L,R]的答案等于[1,R]的答案减去[1,L-1]的答案。这个套路在计数题里太常用了几乎成了条件反射。P1980本身是[1,n]正是这个函数的最简形态。类似的题目在洛谷上有很多比如 P2602 [ZJOI2010] 数字计数就是要求统计一个区间里0到9每个数字出现的次数。数据范围可以到10^12暴力显然不可能但用按位计数法稍作扩展就能搞定。你会发现P1980的那个分类讨论在P2602里变成内层循环枚举0到9逻辑几乎一模一样。所以我说这道普及组第一题是后续很多题目的种子。5.2 由“计数问题”想到的数位DP再往深处走一点按位计数法其实就是数位DP的最简版本。数位DP处理的往往是“某一位上满足某些条件的数字个数”比如“不含4的数字”“包含至少一个6的数字”。这类问题本质上是在按位枚举时维护状态P1980的按位统计可以看作是数位DP里“只需要统计出现次数不需要记录复杂状态”的特例。如果你以后准备挑战提高组建议在掌握P1980后按这个顺序练习先做 P1980再做 P2602然后尝试数位DP的经典题。你会发现它们共用一套“高位、当前位、低位”的拆解框架。有时候竞赛里遇到新题表面上是动态规划实际上底层就是计数问题的升级版基础扎实了思路会顺很多。我记得有一年NOIP提高组有一道题叫愤怒的小鸟那个题开起来是状态压缩DP跟数字计数八竿子打不着。但里面那种“枚举子集转移”的基础能力也是从一道一道简单题里练出来的。P1980虽然简单但它教会我的不是代码而是“把复杂统计拆成独立贡献”的思维模式这个模式在愤怒的小鸟这类题里同样有用。5.3 一点个人经验我在实际使用这个函数时最大的心得是写计数类函数一定要先想清楚“输入边界”和“前导零规则”。很多时候出bug不是因为公式不熟而是因为没想清楚函数被调用时的上下文。比如统计0的时候你是在统计“十进制表示中的0”还是在统计“包含前导0的定长字符串中的0”这两种规则完全不同。P1980明确告诉我们不要前导零。所以 x0 的那条分支天然比 x0 复杂。以后遇到任何数字统计题目第一件事是问自己这里允许前导零吗如果允许公式马上变化如果不允许就要记得在最高位或者 cur0 时做特殊处理。另外对拍验证真的是个好东西。我第一次写按位计数时靠肉眼检查样例以为对了结果在 n101、x0 这种数据上露馅。后来我把暴力版和优化版都写好用随机数据对拍一次性能揪出一堆问题。对于这种逻辑不太复杂的题目对拍的成本极低收益却很高推荐你也养成这个习惯。