洛谷P3311 [SDOI2014] 数数 题解

题目链接：P3311 [SDOI2014] 数数

题意：

我们称一个正整数 $x$ 是幸运数，当且仅当它的十进制表示中不包含数字串集合 $s$ 中任意一个元素作为其子串。例如当 $s = \{22, 333, 0233\}$ 时，$233$ 是幸运数，$2333$、$20233$、$3223$ 不是幸运数。给定 $n$ 和 $s$，计算不大于 $n$ 的幸运数个数。

答案对 $10^9 + 7$ 取模。

$1 \leq n < 10^{1201}$，$1 \leq m \leq 100$，$1 \leq \sum_{i = 1}^m |s_i| \leq 1500$，$\min_{i = 1}^m |s_i| \geq 1$，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。$n$ 没有前导 $0$，但是 $s_i$ 可能有前导 $0$。

关键词：数位dp、AC自动机

可能的前置芝士：P4052 [JSOI2007]文本生成器 （涉及“危险结点”的定义）

和P4052一样，我们先建出 $\tt{AC}$ 自动机，然后找到所有的危险结点

因为这道题要求答案不超过 $n$ ，并且 $n < 10^{1201}$ ，考虑数位dp

设 $f_{i,j}$ 表示考虑 $n$ 的前 $i$ 位（从高位向低位数），走到 $\tt{AC}$ 自动机的 $j$ 结点的答案。

然后用记搜搞搞就好了，懒得写转移方程，直接看代码

值得注意的是，如果数位dp的过程中 $j$ 走到了危险结点，

则要立刻返回 $0$ ，因为不能包含任何的非法子串 $s_i$

时间复杂度 $O(n \times \sum |s_i|)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1515)

const int mod=1e9+7;
int n,num[N],f[N][N];
struct Trie
{
    bitset<N> ed;
    int tot,fail[N],trie[N][10];
    void insert(string s)
    {
        int u=0;
        for(int i=0; i<s.size(); i++)
        {
            char c=s[i]-'0';
            if(!trie[u][c]) trie[u][c]=++tot;
            u=trie[u][c];
        }
        ed[u]=1;
    }
    void build()
    {
        queue<int> q;
        for(int i=0; i<10; i++)
            if(trie[0][i]) q.push(trie[0][i]);
        while(!q.empty())
        {
            int u=q.front(); q.pop();
            for(int i=0; i<10; i++)
            {
                if(trie[u][i])
                {
                    fail[trie[u][i]]=trie[fail[u]][i];
                    if(ed[fail[trie[u][i]]]) ed[trie[u][i]]=1;
                    q.push(trie[u][i]);
                }else trie[u][i]=trie[fail[u]][i];
            }
        }
    }
}tr;
void add(int &x,int y){ (x+=y) >= mod ? x-=mod : 0;}
int dfs(int u,int pos,bool limit,bool qd0)
{
    if(!u) return !tr.ed[pos];
    if(tr.ed[pos]) return 0;
    if(!limit&&!qd0&&f[u][pos]!=-1) return f[u][pos];
    int res=0,up=limit?num[u]:9;
    for(int i=0; i<=up; i++)
    {
        if(!i&&qd0) add(res,dfs(u-1,0,limit&&num[u]==i,1));
        else add(res,dfs(u-1,tr.trie[pos][i],limit&&num[u]==i,0));
    }
    if(!limit&&!qd0) f[u][pos]=res;
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    string s; cin >> s >> n;
    int len=s.size();
    for(int i=0; i<len; i++) num[len-i]=s[i]-'0';
    for(int i=1; i<=n; i++) cin >> s,tr.insert(s);
    
    tr.build(); memset(f,-1,sizeof(f));
    int ans=dfs(len,0,1,1); add(ans,mod-1); // no 0
    cout << ans << '\n';
    return 0;
}