企业官网建设流程全解析

题目描述

给定一个正整数NNN和一个正整数MMM（长度可达100100100位，以字符串形式给出，无前导零），数字MMM被视为不吉利的数字。一个NNN位数（首位不能为000，但当N=1N = 1N=1时允许该位为000）如果其十进制表示中不包含子串MMM，则称为幸运数字。

请计算满足条件的幸运数字的个数。结果可能很大，对100000071000000710000007取模。

输入格式

第一行包含一个整数TTT（T≤1000T \le 1000T≤1000），表示测试用例数。
接下来TTT行，每行两个正整数NNN和MMM，其中NNN是一个整数（1≤N≤1001 \le N \le 1001≤N≤100），MMM是一个可能长达100100100位的数字字符串。

输出格式

对于每个测试用例，输出一行一个整数，表示幸运数字的个数对100000071000000710000007取模的结果。

样例

输入

3 1 3 2 13 2 1

输出

9 89 72

样例解释

• N=1N = 1N=1，M=3M = 3M=3：一位数字有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）。
• N=2N = 2N=2，M=13M = 13M=13：所有两位数为10∼9910 \sim 9910∼99，共909090个，其中包含13的只有131313这一个，故答案为898989。
• N=2N = 2N=2，M=1M = 1M=1：所有两位数中，十位不能为000，且不含1。十位可取2∼92 \sim 92∼9（888种），个位可取0,2∼90,2 \sim 90,2∼9（999种），共8×9=728 \times 9 = 728×9=72。

题目分析

本题的核心是计数长度为NNN、首位非零且不包含给定模式串MMM的数字串个数。由于NNN很小（N≤100N \le 100N≤100），但MMM可以很长（100100100位），因此不能枚举数字串，而是需要利用自动机状态转移进行动态规划。

考虑先放宽限制，允许前导零，计算长度为LLL的任意数字串（允许前导零）中不含MMM的个数，记为f(L)f(L)f(L)。那么最终答案可以通过容斥得到：

• 当N=1N = 1N=1时，首位为零的数字就是0，它不含任何正整数MMM（因为M≥1M \ge 1M≥1），因此答案就是f(1)f(1)f(1)。
• 当N>1N > 1N>1时，首位为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自动机

1. 对模式串MMM计算前缀函数（next\textit{next}next数组）。
2. 对于每个状态sss（0≤s<∣M∣0 \le s < |M|0≤s<∣M∣）和每个数字ddd（0∼90 \sim 90∼9），模拟KMP\texttt{KMP}KMP匹配过程，得到新状态s′s's′。如果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′s's′不是∣M∣|M|∣M∣，则进行累加：

dp[ℓ+1][s′]+=dp[ℓ][s] \textit{dp}[\ell+1][s'] \mathrel{+}= \textit{dp}[\ell][s]dp[ℓ+1][s′]+=dp[ℓ][s]

所有运算取模100000071000000710000007。最终：

f(L)=∑s=0∣M∣−1dp[L][s] f(L) = \sum_{s=0}^{|M|-1} \textit{dp}[L][s]f(L)=s=0∑∣M∣−1​dp[L][s]

由于N≤100N \le 100N≤100，直接递推即可。

答案计算

• 若N=1N = 1N=1，答案为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∣≤100，T≤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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;constintMOD=10000007;while(T--){intN;string M;cin>>N>>M;intlen=(int)M.size();// 构建 KMP 前缀函数vector<int>nextArr(len,0);for(inti=1;i<len;++i){intj=nextArr[i-1];while(j>0&&M[i]!=M[j])j=nextArr[j-1];if(M[i]==M[j])++j;nextArr[i]=j;}// 构建自动机转移表 trans[state][digit] -> 新状态（可能等于 len，表示完全匹配）vector<vector<int>>trans(len,vector<int>(10,0));for(intstate=0;state<len;++state){for(intdigit=0;digit<10;++digit){charc=char('0'+digit);intns=state;while(ns>0&&M[ns]!=c)ns=nextArr[ns-1];if(M[ns]==c)++ns;trans[state][digit]=ns;// 可能为 len}}// dp[length][state]：长度 length 的串，匹配状态为 state 的方案数（允许前导零）vector<vector<int>>dp(N+1,vector<int>(len,0));dp[0][0]=1;vector<int>f(N+1,0);f[0]=1;// 空串for(intlength=1;length<=N;++length){for(intstate=0;state<len;++state){intcur=dp[length-1][state];if(cur==0)continue;for(intdigit=0;digit<10;++digit){intns=trans[state][digit];if(ns<len){// 未完全匹配 M，合法dp[length][ns]=(dp[length][ns]+cur)%MOD;}}}intsum=0;for(intstate=0;state<len;++state)sum=(sum+dp[length][state])%MOD;f[length]=sum;}intans;if(N==1)ans=f[1];elseans=(f[N]-f[N-1]+MOD)%MOD;cout<<ans<<'\n';}return0;}

总结

本题是一道典型的基于KMP\texttt{KMP}KMP自动机的计数动态规划问题。关键技巧在于：

• 利用KMP\texttt{KMP}KMP的失配指针构建自动机，将“不包含子串”的约束转化为状态转移的合法性判断。
• 采用容斥思想，先计算允许前导零的答案，再减去首位为零的情况，从而得到最终合法的NNN位数个数。
• 由于NNN和MMM的长度都很小，直接二维dp\texttt{dp}dp递推即可，无需矩阵快速幂等高级优化。

这种方法同样适用于其他类似的“不包含给定模式串”的数字计数问题，只需将模式串长度和NNN的规模适当调整即可。处理大模数时注意取模操作，避免负数。