模板洛谷p3311
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
// 常量定义:N为AC自动机状态数上限、数位DP位数上限;mod为答案取模值
const int N=2010,mod=1e9+7;// AC自动机核心数组:
// tr[状态][数字] = 下一个状态(转移表);fail[状态] = 失败指针;idx为状态计数器
int tr[N][10],fail[N],idx;
// alert[状态]:标记该状态是否对应包含禁忌子串(含fail链继承的禁忌)
bool alert[N];// 数位DP相关变量:
// m为禁忌串数量;d[位]:存储数字n的每一位(从低位到高位);have0标记是否有禁忌串"0"
int m,d[N],have0;
// dp[当前位][AC自动机状态]:记忆化存储“当前处理到第pos位,AC状态为cur,无限制且无前导零”时的合法数个数
LL dp[N][N];// 功能:将单个禁忌串插入AC自动机
// 参数:s为待插入的禁忌数字串
void insert(string& s){int cur=0; // 从AC自动机根节点(状态0)开始for(char& ch:s){ // 遍历禁忌串的每个字符int path=ch-'0'; // 将字符转为数字(0-9),作为转移路径if(!tr[cur][path]) // 若当前状态cur没有path方向的子节点,创建新状态tr[cur][path]=++idx;cur=tr[cur][path]; // 转移到下一个状态}alert[cur]=true; // 标记当前状态(禁忌串结尾)为“含禁忌子串”
}// 功能:初始化AC自动机的失败指针(BFS实现),构建fail链
void init(){queue<int> q; // BFS队列,存储待处理的AC状态// 初始化队列:将根节点(状态0)的所有直接子节点加入队列for(int i=0;i<10;i++){if(tr[0][i]){ // 若根节点有数字i方向的子节点q.push(tr[0][i]);}}while(q.size()){ // BFS循环处理每个状态int u=q.front(); // 取出队首状态uq.pop();for(int i=0;i<10;i++){ // 遍历u的所有可能转移方向(0-9)if(tr[u][i]){ // 情况1:u有数字i方向的子节点// 子节点的失败指针 = u的失败指针在i方向的转移状态fail[tr[u][i]]=tr[fail[u]][i];// 子节点是否含禁忌 = 自身是否禁忌 或 失败指针指向的状态是否禁忌(继承fail链的禁忌)alert[tr[u][i]]|=alert[fail[tr[u][i]]];q.push(tr[u][i]); // 将子节点加入队列,后续处理}else{ // 情况2:u无数字i方向的子节点,路径压缩(直接指向fail链的转移结果)tr[u][i]=tr[fail[u]][i];}}}
}// 功能:数位DP记忆化搜索,统计“当前状态下合法的数字个数”
// 参数:
// pos:当前处理的位数(从高位到低位,最终到0位结束)
// limit:是否受原数字n的当前位限制(true=只能填≤n的当前位,false=可填0-9)
// zero:是否处于前导零状态(true=前面全是0,当前填0仍为前导零,false=已出现非零数字)
// cur:当前在AC自动机中的状态(跟踪是否包含禁忌子串)
LL dfs(int pos,bool limit,bool zero,int cur){if(pos==0){ // 递归终止:处理完所有位,计数1个合法数字(空串/已形成完整数字)return 1;}// 记忆化复用:若“无限制、无前导零、状态已计算过”,直接返回存储的结果if(!limit&&!zero&&~dp[pos][cur])return dp[pos][cur];// 确定当前位的最大可填数字:受限时为n的当前位(d[pos]),否则为9int up=limit?d[pos]:9;LL ret=0; // 存储当前状态下的合法数个数for(int i=0;i<=up;i++){ // 遍历当前位可填的所有数字(0到up)int tmp=tr[cur][i]; // 计算当前数字i对应的AC状态转移结果if(i==0&&zero) // 若当前是前导零且填0,AC状态保持根节点(0)(避免前导零计入禁忌判断)tmp=0;if(alert[tmp]) // 若当前AC状态含禁忌子串,跳过该数字(不合法)continue;// 递归处理下一位:// 新limit = 原limit且当前填的数字等于up(仍受限制)// 新zero = 原zero且当前填的数字等于0(仍为前导零)// 新cur = 计算出的AC状态tmp(ret+=dfs(pos-1,limit&&(i==d[pos]),zero&&(i==0),tmp))%=mod;}// 记忆化存储:仅当“无限制、无前导零”时,保存当前状态的结果(后续可复用)if(!limit&&!zero)dp[pos][cur]=ret;return ret;
}// 功能:计算“0到n之间所有不含禁忌子串的数字个数”
// 参数:s为原数字n的字符串形式
LL calc(string &s){memset(dp,0xff,sizeof(dp)); // 初始化记忆化数组为-1(标记未计算)int len=s.size(); // 原数字n的位数// 将字符串s的数字从后往前存入d数组(d[1]是个位,d[len]是最高位)// 目的:配合数位DP从高位(pos=len)到低位(pos=1)的处理顺序for(int i=len-1,j=1;i>=0;i--,j++){d[j]=s[i]-'0';}// 调用DFS:从最高位(len)开始,初始状态为“受限制、前导零、AC根节点”return dfs(len,1,1,0)%mod;
}int main(){// 关闭同步,加速cin输入(处理大输入时有效)cin.tie(nullptr)->sync_with_stdio(false);string n; // 存储原数字n(字符串形式,应对超大数据)cin>>n;cin>>m; // 读取禁忌串的数量for(int i=1;i<=m;i++){ // 遍历每个禁忌串string s;cin>>s;insert(s); // 插入AC自动机if(s=="0") // 标记是否存在禁忌串“0”(后续用于判断是否需扣除0的计数)have0=1;}init(); // 初始化AC自动机的失败指针// 计算最终答案:// calc(n) = 0~n的合法数个数;!have0 = 0是否合法(1=合法,0=非法)// 题目要求“不大于n的正整数”,需扣除0的计数(若0合法)cout<<(calc(n)-!have0+mod)%mod<<endl;return 0;
}