知识点:ACAM,数位 DP
原题面:Luogu
简述
给定一个整数 \(n\),一大小为 \(m\) 的数字串集合 \(s\)。
求不以 \(s\) 中任意一个数字串作为子串的,不大于 \(n\) 的数字的个数。
\(1\le n\le 10^{1201}\),\(1\le m\le 100\),\(1\le \sum |s_i|\le 1500\)。\(n\) 没有前导零,\(s_i\) 可能存在前导零。
1S,128MB。
分析
题目要求不以 \(s\) 中任意一个数字串作为子串,想到这题:「JSOI2007」文本生成器。首先套路地对给定集合的串构建 ACAM,并在 ACAM 上标记所有包含集合内的子串的状态。
之后考虑在 ACAM 上模拟串匹配的过程做数位 DP。发现前缀所在状态储存了前缀的所有信息,可以将其作为 dfs 的参数。
设 Dfs(int now_, int pos_, bool zero_, bool lim_) {
表示前缀匹配到的 ACAM 的状态为 \(\operatorname{pos}\) 时,合法的数字的数量。转移时沿 ACAM 上的转移函数转移,避免转移到被标记的状态。
存在 \(\operatorname{trans}(0, 0) = 0\),这样直接 dfs 也能顺便处理不同长度的数字串。
总复杂度 \(O(\log_{10}(n)\sum |s_i|)\) 级别。
代码
//知识点:ACAM,数位 DP
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
const int kN = 1500 + 10;
const int mod = 1e9 + 7;
//=============================================================
int n, m, ans;
char num[kN], s[kN];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void Chkmin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
namespace ACAM {
const int kSigma = 10;
int node_num, tr[kN][kSigma], last[kN], fail[kN];
int f[kN][kN];
bool tag[kN];
void Insert(char *s_) {
int u_ = 0, lth = strlen(s_ + 1);
for (int i = 1; i <= lth; ++ i) {
if (! tr[u_][s_[i] - '0']) tr[u_][s_[i] - '0'] = ++ node_num;
u_ = tr[u_][s_[i] - '0'];
last[u_] = s_[i] - '0';
}
tag[u_] = true;
}
void Build() {
std:: queue <int> q;
for (int i = 0; i < kSigma; ++ i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (!q.empty()) {
int u_ = q.front(); q.pop();
tag[u_] |= tag[fail[u_]];
for (int i = 0; i < kSigma; ++ i) {
int v_ = tr[u_][i];
if (v_) {
fail[v_] = tr[fail[u_]][i];
q.push(v_);
} else {
tr[u_][i] = tr[fail[u_]][i];
}
}
}
}
int Dfs(int now_, int pos_, bool zero_, bool lim_) {
if (now_ > n) return 1;
if (!zero_ && !lim_ && f[now_][pos_] != -1) return f[now_][pos_];
int ret = 0;
for (int i = 0, up = lim_ ? num[now_] - '0': 9; i <= up; ++ i) {
int v_ = tr[pos_][i];
if (tag[v_]) continue;
if (zero_ && !i) ret += Dfs(now_ + 1, 0, true, lim_ && i == num[now_] - '0');
else ret += Dfs(now_ + 1, v_, false, lim_ && i == num[now_] - '0');
ret %= mod;
}
if (!zero_ && !lim_) f[now_][pos_] = ret;
return ret;
}
int DP() {
memset(f, -1, sizeof (f));
return Dfs(1, 0, true, true);
}
}
//=============================================================
int main() {
scanf("%s", num + 1);
n = strlen(num + 1);
m = read();
for (int i = 1; i <= m; ++ i) {
scanf("%s", s + 1);
ACAM::Insert(s);
}
ACAM::Build();
printf("%d\n", ACAM::DP());
return 0;
}