UVa 12040 Again Lucky Numbers-北京尧图网络

题目描述给定一个正整数NNN和一个正整数MMM长度可达100100100位以字符串形式给出无前导零数字MMM被视为不吉利的数字。一个NNN位数首位不能为000但当N1N 1N1时允许该位为000如果其十进制表示中不包含子串MMM则称为幸运数字。请计算满足条件的幸运数字的个数。结果可能很大对100000071000000710000007取模。输入格式第一行包含一个整数TTTT≤1000T \le 1000T≤1000表示测试用例数。接下来TTT行每行两个正整数NNN和MMM其中NNN是一个整数1≤N≤1001 \le N \le 1001≤N≤100MMM是一个可能长达100100100位的数字字符串。输出格式对于每个测试用例输出一行一个整数表示幸运数字的个数对100000071000000710000007取模的结果。样例输入3 1 3 2 13 2 1输出9 89 72样例解释N1N 1N1M3M 3M3一位数字有0∼90 \sim 90∼9其中不含3的有999个0,1,2,4,5,6,7,8,90,1,2,4,5,6,7,8,90,1,2,4,5,6,7,8,9。N2N 2N2M13M 13M13所有两位数为10∼9910 \sim 9910∼99共909090个其中包含13的只有131313这一个故答案为898989。N2N 2N2M1M 1M1所有两位数中十位不能为000且不含1。十位可取2∼92 \sim 92∼9888种个位可取0,2∼90,2 \sim 90,2∼9999种共8×9728 \times 9 728×972。题目分析本题的核心是计数长度为NNN、首位非零且不包含给定模式串MMM的数字串个数。由于NNN很小N≤100N \le 100N≤100但MMM可以很长100100100位因此不能枚举数字串而是需要利用自动机状态转移进行动态规划。考虑先放宽限制允许前导零计算长度为LLL的任意数字串允许前导零中不含MMM的个数记为f(L)f(L)f(L)。那么最终答案可以通过容斥得到当N1N 1N1时首位为零的数字就是0它不含任何正整数MMM因为M≥1M \ge 1M≥1因此答案就是f(1)f(1)f(1)。当N1N 1N1时首位为000的串有10N−110^{N-1}10N−1个但不含MMM的个数等于f(N−1)f(N-1)f(N−1)因为MMM不以000开头所以首位000不会产生匹配影响。因此实际答案为f(N)−f(N−1)f(N) - f(N-1)f(N)−f(N−1)。现在核心问题是计算f(L)f(L)f(L)。我们可以在每个位置依次填入数字并动态维护当前已匹配MMM的前缀长度。这与字符串匹配中的KMP\texttt{KMP}KMP自动机一致状态表示当前已经匹配到MMM的哪个前缀位置000到∣M∣−1|M|-1∣M∣−1。当读入一个数字ddd后根据MMM的失配函数转移到新状态。若新状态等于∣M∣|M|∣M∣则说明完整地出现了MMM该转移非法否则合法。由于NNN只有100100100状态数最多为∣M∣≤100|M| \le 100∣M∣≤100转移数101010因此可以直接递推。解题思路构建KMP\texttt{KMP}KMP自动机对模式串MMM计算前缀函数next\textit{next}next数组。对于每个状态sss0≤s∣M∣0 \le s |M|0≤s∣M∣和每个数字ddd0∼90 \sim 90∼9模拟KMP\texttt{KMP}KMP匹配过程得到新状态s′ss′。如果s′∣M∣s |M|s′∣M∣表示匹配到了完整的MMM则这个转移不可用否则可用。动态规划计算f(L)f(L)f(L)定义dp[ℓ][s]\textit{dp}[\ell][s]dp[ℓ][s]表示长度为ℓ\ellℓ、且当前匹配状态为sss的合法数字串个数允许前导零。初始dp[0][0]1\textit{dp}[0][0] 1dp[0][0]1。对于每个ℓ\ellℓ枚举所有状态sss然后尝试每个数字ddd若转移到的s′ss′不是∣M∣|M|∣M∣则进行累加dp[ℓ1][s′]dp[ℓ][s] \textit{dp}[\ell1][s] \mathrel{} \textit{dp}[\ell][s]dp[ℓ1][s′]dp[ℓ][s]所有运算取模100000071000000710000007。最终f(L)∑s0∣M∣−1dp[L][s] f(L) \sum_{s0}^{|M|-1} \textit{dp}[L][s]f(L)s0∑∣M∣−1dp[L][s]由于N≤100N \le 100N≤100直接递推即可。答案计算若N1N 1N1答案为f(1)f(1)f(1)。否则答案为(f(N)−f(N−1)MOD) mod MOD(f(N) - f(N-1) \textit{MOD}) \bmod \textit{MOD}(f(N)−f(N−1)MOD)modMOD。复杂度分析对于每个测试用例构建自动机需O(∣M∣⋅10)O(|M| \cdot 10)O(∣M∣⋅10)递推需O(N⋅∣M∣⋅10)O(N \cdot |M| \cdot 10)O(N⋅∣M∣⋅10)。总时间复杂度O(T⋅(N⋅∣M∣⋅10))O(T \cdot (N \cdot |M| \cdot 10))O(T⋅(N⋅∣M∣⋅10))在N,∣M∣≤100N, |M| \le 100N,∣M∣≤100T≤1000T \le 1000T≤1000时约为10810^8108次运算可接受。空间复杂度O(∣M∣)O(|M|)O(∣M∣)存储转移表和dp\textit{dp}dp数组若一次性构建转移表则为O(∣M∣⋅10)O(|M| \cdot 10)O(∣M∣⋅10)。代码实现// Again Lucky Numbers// UVa ID: 12040// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.030s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;constintMOD10000007;while(T--){intN;string M;cinNM;intlen(int)M.size();// 构建 KMP 前缀函数vectorintnextArr(len,0);for(inti1;ilen;i){intjnextArr[i-1];while(j0M[i]!M[j])jnextArr[j-1];if(M[i]M[j])j;nextArr[i]j;}// 构建自动机转移表 trans[state][digit] - 新状态可能等于 len表示完全匹配vectorvectorinttrans(len,vectorint(10,0));for(intstate0;statelen;state){for(intdigit0;digit10;digit){charcchar(0digit);intnsstate;while(ns0M[ns]!c)nsnextArr[ns-1];if(M[ns]c)ns;trans[state][digit]ns;// 可能为 len}}// dp[length][state]长度 length 的串匹配状态为 state 的方案数允许前导零vectorvectorintdp(N1,vectorint(len,0));dp[0][0]1;vectorintf(N1,0);f[0]1;// 空串for(intlength1;lengthN;length){for(intstate0;statelen;state){intcurdp[length-1][state];if(cur0)continue;for(intdigit0;digit10;digit){intnstrans[state][digit];if(nslen){// 未完全匹配 M合法dp[length][ns](dp[length][ns]cur)%MOD;}}}intsum0;for(intstate0;statelen;state)sum(sumdp[length][state])%MOD;f[length]sum;}intans;if(N1)ansf[1];elseans(f[N]-f[N-1]MOD)%MOD;coutans\n;}return0;}总结本题是一道典型的基于KMP\texttt{KMP}KMP自动机的计数动态规划问题。关键技巧在于利用KMP\texttt{KMP}KMP的失配指针构建自动机将“不包含子串”的约束转化为状态转移的合法性判断。采用容斥思想先计算允许前导零的答案再减去首位为零的情况从而得到最终合法的NNN位数个数。由于NNN和MMM的长度都很小直接二维dp\texttt{dp}dp递推即可无需矩阵快速幂等高级优化。这种方法同样适用于其他类似的“不包含给定模式串”的数字计数问题只需将模式串长度和NNN的规模适当调整即可。处理大模数时注意取模操作避免负数。

UVa 12040 Again Lucky Numbers

相关推荐

UVa 13197 Cuberoot This

IDEA内置终端npm -v报错？根因排查与修复指南

PCA9422+PIC32MX构建可编程电源管理子系统

更多资讯

从Hugging Face到GPU推理：大模型本地部署与工程化落地实战

机器学习驱动的英雄联盟胜负预测与Django部署实战

Hugging Face与NVIDIA GPU集成实战：模型加载、显存优化与推理部署

从Transformer到物理AI：长上下文瓶颈与线性注意力、状态空间模型解析

电销语音机器人完整版源码部署与安装教程：从软交换到外呼落地

PS5游戏元数据解析工具开发指南

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？