如果你刷算法题时刷到洛谷这类OJ的P开头编号看到“P3499 幸运数字”这个名字第一反应大概率是“又一道数论题”。但我把这题做完之后发现它披着“幸运数字”的外衣内核其实是个非常经典的字典序编号问题给定一个只由4和7组成的数字集合求第n个数字或者统计某个区间内有多少个这样的数字。只要你抓住了“二进制映射”这个点整道题的代码可以短到十几行而且不容易错。本文就按这个思路来拆先讲清楚幸运数字这个集合的顺序规律再给出从暴力到打表、再到二进制定位的完整推导过程最后把区间计数的扩展做法和容易翻车的边界细节一起讲掉。适合刚接触这类“第K个数字”题目的新手也适合想复习计数类思路的竞赛选手。1. 读懂题面背后的顺序规律幸运数字本质上是字典序编号1.1 经典题面与两种常见问法这类题在不同题库里定义会有细微差别但最经典的版本是这样的一个正整数如果它的十进制表示中每一位都只含有4和7就称它为幸运数字。从小到大列出这些数字前几个是4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777, 4444, ...题目最常见的问法有两种给定n输出第n个幸运数字给定区间[l, r]统计这个区间内幸运数字的个数。第二种问法还经常变形成“区间内第k个幸运数字是谁”本质上是一样的套路。很多第一次做这道题的人会先去枚举所有数字逐个判断是不是只含4和7。这个思路本身没错但它完全没有看到这个序列的内在结构所以一旦数据范围变大就会超时。1.2 把4和7翻译成0和1长度分块的威力你盯着上面这个序列看一会儿会发现在字典序也就是字符串比较顺序下有一个非常漂亮的分块结构长度为1的数字有2个4, 7长度为2的数字有4个44, 47, 74, 77长度为3的数字有8个444, 447, 474, 477, 744, 747, 774, 777长度为k的数字正好有2^k个。为什么是2^k因为长度为k的幸运数字每一位只能在4和7里二选一所以排列组合就是2^k。而这个规律意味着整个“所有幸运数字”的集合如果按长度从小到大排每个长度是一个独立的“块”块内部再按字典序排。更关键的一步来了把4看成二进制的0把7看成二进制的1。那么长度为k的幸运数字就和所有k位二进制数一一对应。例如长度为3的块里二进制映射幸运数字000444001447010474011477100744101747110774111777你会发现同长度块内部的字典序正好就是二进制数值从0到2^k-1升序。这不是巧合而是因为4和7两个字符的顺序对应了0和1两个数字的顺序。一旦看到这一层“求第n个幸运数字”就变成了“先确定它属于哪个长度块再在块内把序号翻译成二进制串”。这里有个容易理解偏的点不能直接用十进制整数比较来排全部幸运数字。因为4如果映射成0按整数看它小于一切但在幸运数字序列里所有一位数都排在两位数前面。长度是最高优先级其次才是块内的字典序。所以解题时要始终记得“先分长度块再处理块内偏移”。2. 暴力枚举与打表预处理看起来很简单但为什么不能直接交2.1 逐个判断的复杂度账本先看看大多数人的第一反应。写一个判断函数检查一个数字的十进制每一位是不是只有4和7然后从1开始往上枚举bool isLucky(long long x) { while (x 0) { long long d x % 10; if (d ! 4 d ! 7) return false; x / 10; } return true; }如果要找第n个幸运数字就写个循环从1开始计数每遇到一个幸运数字就把计数器加1直到计数器等于n。这个代码在n很小时完全没问题。但你看一下复杂度从1枚举到目标数字每个数字还要做一次位数级别的判断总复杂度大约O(target * len)。就算题目只要求n是1e6量级你也得枚举到几百万勉强能跑一旦n到1e9甚至1e12直接没戏。更现实的是这类题往往把n设置到1e18附近暴力枚举连边都摸不到。我见过不少新手在这道题上先写暴力然后试图用各种优化去“拯救”暴力比如减少取模次数、用整数缓存等。没用瓶颈是枚举的数字个数本身不是单次判断的速度。2.2 DFS打表什么时候它是可用方案除了逐个枚举另一个常见思路是用DFS递归构造所有幸运数字void dfs(string cur, int len, vectorstring out) { if ((int)cur.size() len) { out.push_back(cur); return; } dfs(cur 4, len, out); dfs(cur 7, len, out); }这样每一层递归决定一位先生成4再生成7正好也符合字典序。如果最高只需要到长度为K的块生成的幸运数字总数是2^1 2^2 ... 2^K 2^(K1) - 2当K20时这个数大约是200万完全可以接受甚至可以直接在本地把所有答案打成一个静态表提交。当K30时数量已经超过20亿时间和内存同时爆炸当K60时那是指数级灾难。所以打表方案是有适用边界的如果题目问第n个幸运数字且n对应的最大长度只有十几二十那么打表是又稳又快的做法如果n到了1e18最大长度接近60那就必须走二进制定位路线。这里也提醒一下很多人做这种题一上来就“打表预处理”其实是在小数据范围内够用但题目稍微改大一点就失灵了。真正值得掌握的是下面这种直接算的方法。3. 核心推导确定长度、计算偏移、做二进制映射3.1 等比数列与最小长度k把序列按长度分块后第一步要确定第n个幸运数字所在块的长度k。记长度不超过k的幸运数字总数为F(k) 2^1 2^2 ... 2^k 2^(k1) - 2要找第n个就是找最小的k使得F(k) n。例如n10F(2)6不够F(3)14够了所以k3。实现上不用真去解不等式直接用一个变量total累加2的幂就行k从1开始int k 1; long long total 0; while (total n) { total (1LL k); k; }循环结束时totalF(k-1)最后一次加进去的那一项是2^(k-1)所以循环结束后k比实际长度多1但要注意处理方式。我更推荐把total和k分开维护写成下面这样更清晰int k 1; long long total 2; // F(1) 2 while (total n) { k; total (1LL k); } // 此时k就是最小满足F(k) n的长度循环结束后长度小于k的所有幸运数字总数是F(k-1) (2^k) - 2所以第n个幸运数字在长度k块内的1-based偏移量pos n - (F(k-1))这个pos一定在[1, 2^k]范围内。接下来就是核心的一步把pos翻译成具体字符串。3.2 偏移量到01串的转换pos-1才是真正的二进制序号现在我们已经知道目标数字长度为k并且在长度为k的块内是第pos个。前面那张表告诉我们同一个块内二进制数值与字典序一一对应且块内第1个对应二进制0第2个对应二进制1依此类推块内第pos个对应二进制值pos-1。所以要先做pos pos - 1再将pos看成k位二进制数。输出时从高位到低位扫描每一位二进制0对应数字4二进制1对应数字7。举例求第3个幸运数字。F(2)6 3所以k2F(1)2pos 3 - 2 1pos-1 0两位二进制是00映射0-40-4得到44。正确。再看第4个pos 4 - 2 2pos-1 1两位二进制是01映射后是47。正确。3.3 完整代码与手算验证核心代码如下#include bits/stdc.h using namespace std; const long long LIMIT 1e18; string kthLuckyNumber(long long n) { // 1. 确定长度k int k 1; long long total 2; // F(1) 2 while (total n) { k; total (1LL k); } // 2. 计算长度k块内的1-based偏移 long long smaller (1LL k) - 2; // F(k-1) 2^k - 2 long long pos n - smaller; // [1, 2^k] // 3. 偏移转k位二进制并映射成4/7 pos--; string ans(k, 4); for (int i 0; i k; i) { // 从高位向低位检查 pos 的第 k-1-i 位 if (pos (1LL (k - 1 - i))) ans[i] 7; else ans[i] 4; } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n; cin n; cout kthLuckyNumber(n) \n; return 0; }来手算几个关键值验证n计算过程输出1k1, smaller0, pos1, pos-10, 二进制042k1, smaller0, pos2, pos-11, 二进制173k2, smaller2, pos1, pos-10, 二进制004410k3, smaller6, pos4, pos-13, 二进制01147714k3, smaller6, pos8, pos-17, 二进制11177715k4, smaller14, pos1, pos-10, 二进制00004444n10对应的序列第10项确实是477n15也正好是长度4块的第一项4444。这说明整套推导是自洽的。这里还要注意一个细节代码里(1LL k)当k比较大有溢出风险。如果n的限制是1e18最大长度k不会超过601LL 60大概在1.15e18还在long long范围内。但如果你把n调大到接近9e18就需要格外小心这一点我在第5节专门讲。4. 从第n个到区间计数前缀和与二分扩展4.1 countUpTo按长度累加再对长度块二分如果题目改成“统计[l, r]范围内有多少个幸运数字”常见的做法是拆成前缀计数差cnt(r) - cnt(l-1)。问题就变成了写一个函数countUpTo(x)统计不超过x的幸运数字数量。有了上一节的基础countUpTo可以这样做如果x 4直接返回0取x的十进制位数k先累加上所有长度小于k的幸运数字总数即2^k - 2再统计长度等于k、且字符串不大于x的幸运数字有多少个。第4步是唯一需要动脑的地方。因为长度为k的幸运数字按字典序排等价于按二进制数0到2^k-1排所以我们可以二分这个块的内部序号。一个朴素的check是用kthLuckyNumber的思想生成块内第mid个长度为k的幸运数字把它和x做字符串比较。不过更稳的写法是直接在长度为k的二进制序号范围[0, 2^k-1]里二分最大的序号mid使得gen(mid) x其中gen的实现和之前pos-1映射完全一样。二分结束后长度等于k且不超过x的个数就是mid1。string genBySeq(int k, long long id) { // id 是长度为k的块内从0开始的序号 string s(k, 4); for (int i 0; i k; i) { if (id (1LL (k - 1 - i))) s[i] 7; } return s; } long long countUpTo(string x) { if (x.size() 1 x[0] 4) return 0; int k (int)x.size(); long long res (1LL k) - 2; // 长度小于k的所有幸运数字总数 long long lo 0, hi (1LL k) - 1; long long best -1; while (lo hi) { long long mid (lo hi) / 2; string cur genBySeq(k, mid); if (cur x) { best mid; lo mid 1; } else { hi mid - 1; } } if (best 0) res best 1; return res; }这个实现的复杂度是O(k^2)k是x的十进制位数最大也就是60左右完全能应付1e18量级的输入。要注意cur x用的是字符串字典序比较因为两者长度相同字符串比较正好等价于数字大小比较。如果你不想二分也可以从高位到低位做贪心统计但二分的简洁性和正确性更好验证。每次二分都要生成一次字符串最多二分60轮实际跑起来非常快。4.2 区间第k个幸运数字与常见变形有了countUpTo很多变体题目都能顺手解决。比如“问[l, r]区间内第k个幸运数字是谁”先算a countUpTo(l-1)、b countUpTo(r)如果k b - a说明区间内没那么多幸运数字输出-1否则第k个就是全局序列中的第a k个直接调用kthLuckyNumber(a k)返回字符串。再比如“输出所有长度不超过n的幸运数字”直接用DFS构造就行和上一节的打表方案一样。还有一类更隐蔽的变形不限定4和7而是给定两个字符d1、d2让你求第n个只由这两个字符组成的数字。本质完全一样只需要把映射那里的4换成d1、7换成d2。理解了“长度分块二进制映射”这种题就是换两个字符的事。5. 现场写题最容易踩的坑边界、溢出与测试用例设计5.1 偏移量减一和长度循环边界两个最常见的翻车点我见过很多提交WA的代码问题几乎都出在两处。第一处是忘记pos-1。块内第1个幸运数字对应二进制0但如果你直接用pos去映射就会导致第1个被映射成二进制1也就是“47”而不是“44”。这种错误非常隐蔽因为小数据你用手算几个容易蒙混过去一旦n稍微大一点就全乱了。第二处是长度循环的边界条件。如果写成while (total n) { ... }当n恰好等于某个F(k)时比如n2total初值是2total n成立会多走一次循环把k变成2最后输出的答案从7变成44。一定要记住长度循环是找到满足F(k) n的最小k当F(k)恰好等于n时就应该停下来。5.2 溢出边界与输入优化再说溢出。1LL k在k62时大约是4.6e18k63时就超了long long的范围属于未定义行为。如果题目给到1e18最大长度k在60以内没有风险但如果题目把上限改到1e18以上或者你的total累加逻辑不够小心就可能在while循环里把1LL k算到溢出。比较保守的做法是提前估算答案的最大长度然后给循环加一个上限判断或者在累加total之前检查1LL k是否超过某个安全值。还有更省心的方案如果你用的是C且确定数据范围很大可以直接用__int128来存中间值但要注意__int128不能直接cin读入得先转成字符串或者long long再赋值。输入优化也是个细节。这类题如果有多组询问记得在main开头加这两行ios::sync_with_stdio(false); cin.tie(nullptr);不然cin处理大量数据时可能平白无故多出不少耗时在在线评测环境里有时候就是TLE和AC的区别。5.3 自测用例表怎么验证自己的写法没毛病最后分享一个我写这类题必做的自测用例表。因为幸运数字序列前几个很容易手推拿这些用例去验证kthLuckyNumber特别高效输入n期望输出说明14第一项27最后一项长度为1344长度2块的第一项677长度2块的最后一项7444长度3块的第一项10477长度3块的第四项14777长度3块最后一项154444长度4块第一项307777F(4)30整块结束3144444长度5块第一项这个表还有一个用途就是验证区间计数的正确性。比如countUpTo(77)应该返回6countUpTo(777)应该返回14而countUpTo(444)应该返回7。跑这个用例时如果答案对不上说明你的countUpTo在边界处理上还有问题。我个人写这类题还有一个习惯写完核心函数后随机生成一些n用DFS打表的答案和kthLuckyNumber的结果互相验证。两者如果在小范围内都一致这个解法基本就稳了。这个交叉验证法对“第K个序列元素”这类题目特别适用因为暴力和打表在数据量小时本身就是完美的参照物。说到底P3499这道题难的地方不在于算法有多高深而在于你能不能从“一堆字符串”里看出“二进制编号”这个结构。一旦你看透了长度分块和4/7映射这两件事后面的代码就是顺水推舟的事。以后遇到任何由少量固定字符组成的“XX数字”题目第一步都该想进制映射而不是硬生生去枚举。