P1590 失踪的7网页链接P1590 失踪的7题目描述远古的 Pascal 人也使用阿拉伯数字来进行计数但是他们又不喜欢使用7 77因为他们认为7 77是一个不吉祥的数字所以 Pascal 数字8 88其实表示的是自然数中的7 7718 1818表示的是自然数中的16 1616。请计算在正整数n nn范围以内包含有多少个 Pascal 数字。输入格式第一行为正整数t tt接下来t tt行每行一个正整数n nn且保证输入的n nn是 Pascal 数字输出格式对于每个正整数n nn输出n nn以内的 Pascal 数的个数。输入输出样例 #1输入 #12 10 20输出 #19 18说明/提示对于所有数据1 ≤ t ≤ 10000 1 \leq t \leq 100001≤t≤100001 ≤ n ≤ 2 32 − 1 1 \leq n \leq 2^{32}-11≤n≤232−1。解题思路本题要求统计从1 11到给定正整数n nn中不含数字7 77的数的个数。由于n nn最大可达2 32 − 1 2^{32}-1232−1且询问次数较多采用数位 DP高效统计[ 0 , n ] [0, n][0,n]内不含7 77的整数个数最后减去0 00即可。1. 问题等价转化所谓 Pascal 数字就是十进制表示中不含数字7 77的正整数。给定一个 Pascal 数字n nn要求1 ∼ n 1 \sim n1∼n中 Pascal 数字的数量等价于求[ 0 , n ] [0, n][0,n]中不含7 77的整数个数再减去1 11去掉数字0 00。因此核心是计算≤ n \le n≤n且数位中不出现7 77的非负整数个数。2. 数位 DP 设计状态定义dfs(pos, lim)表示当前处理到从高位数的第pos位lim标记前几位是否达到上界。返回在后续低位任意填且不出现7 77的方案数。转移枚举当前位可填数字0 ∼ u p 0\sim up0∼up若lim为真up为当前位上限否则为9 99。若枚举数字为7 77则跳过否则累加递归结果。记忆化当lim false时当前状态只与pos有关可以用数组f[pos]记录避免重复计算。分解数位将x xx的十进制各位存入数组d从高位到低位调用dfs(len-1, true)。3. 算法步骤初始化记忆化数组f为− 1 -1−1。对每个询问n nn将n nn拆分为十进制数位。计算res dfs(最高位, true)得到[ 0 , n ] [0, n][0,n]中不含7 77的整数个数。输出res - 1即[ 1 , n ] [1, n][1,n]中的 Pascal 数字个数。4. 复杂度分析时间复杂度数位 DP 状态数O ( 位数 × 2 ) O(\text{位数} \times 2)O(位数×2)每个状态枚举0 ∼ 9 0\sim 90∼9总复杂度O ( 10 ⋅ L ) O(10 \cdot L)O(10⋅L)其中L ≤ 10 L \le 10L≤102 32 − 1 2^{32}-1232−1最多十位。t ≤ 10 4 t \le 10^4t≤104总运算量极小。空间复杂度O ( L ) O(L)O(L)存储数位数组和记忆化数组。总结利用数位 DP 记忆化搜索逐位枚举并跳过数字7 77快速计算[ 0 , n ] [0, n][0,n]中不含7 77的整数数量。最后减去0 00即得答案。该方法能高效处理多组大范围询问。代码简要说明calc(x)将x xx拆位后调用dfs返回[ 0 , x ] [0, x][0,x]中不含7 77的整数个数。dfs(pos, lim)递归统计当前状态下的合法数字个数lim限制当前位是否达到上限非限制状态下使用记忆化f[pos]优化。主函数读入每个n nn输出calc(n) - 1。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll d[1100],len;ll f[1100];lldfs(ll pos,boollim){if(pos-1)return1;if(!limf[pos]!-1)returnf[pos];ll uplim?d[pos]:9;ll ret0;for(ll i0;iup;i){if(i7)continue;retdfs(pos-1,limid[pos]);}if(!lim)f[pos]ret;returnret;}llcalc(ll x){len0;while(x){d[len]x%10;x/10;}returndfs(len-1,true);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(f,-1,sizeof(f));ll T;scanf(%lld,T);while(T--){ll x;scanf(%lld,x);printf(%lld\n,calc(x)-1);}return0;}