洛谷-P4052+P3311 （AC自动机+数位DP）

洛谷-P4052 文本生成器

虽然这题应该称为记忆化搜索，但是就想当做数位DP(QAQ)
一开始数组开小了，导致了WA，TLE，RE以及两个AC，深深的体会到了数组开小了什么错误都有，哈哈

题意：给出一个字典，求长度为M且包含字典中至少一个单词的文本有多少个。

思路：

虽然是要求可读文本的数量，但是毕竟要构造多字符串的匹配还是比较麻烦的，因此可以转化为求总文本数-不可读文本数
转化后总文本数可以直接快速幂搞定，不可读文本数可以在AC自动机上跑数位DP，别跑那些认识的单词就行啦！

题目描述

JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。

该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6

生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助吗？

输入格式

输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (<= 60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包含英文大写字母A…Z

输出格式

一个整数，表示可能的文章总数。只需要知道结果模10007的值。

输入输出样例

输入
2 2
A
B
输出
100

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 2e4+10;
const int mod = 1e4+7;
const double eps = 1e-9;

int N, M;
char s[110];
int trie[maxn][26], fail[maxn], ed[maxn], cnt;
int dp[110][maxn];

int fast(int a, int k) {
    if(!k) return 1;
    int now=fast(a,k/2);
    now=now*now%mod;
    if(k&1) now=now*a%mod;
    return now;
}

void insert() {
    int len=strlen(s), p=0;
    for(int i=0; i<len; ++i) {
        int k=s[i]-'A';
        if(!trie[p][k]) trie[p][k]=++cnt;
        p=trie[p][k];
    }
    ed[p]=1;
}

void build() {
    queue<int> q;
    for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(int i=0; i<26; ++i) {
            if(trie[now][i]) {
                fail[trie[now][i]]=trie[fail[now]][i];
                if(ed[trie[fail[now]][i]]) ed[trie[now][i]]=1;
                q.push(trie[now][i]);
            }
            else trie[now][i]=trie[fail[now]][i];
        }
    }
}

int dfs(int pos, int now) {
    if(pos>M) return 1;
    if(~dp[pos][now]) return dp[pos][now];
    int ans=0;
    for(int i=0; i<26; ++i)
        if(!ed[trie[now][i]]) ans+=dfs(pos+1,trie[now][i]);
    return dp[pos][now]=ans%mod;
}

int main() {
    //ios::sync_with_stdio(false);
    N=read(), M=read();
    for(int i=0; i<N; ++i) scanf("%s", s), insert();
    build();
    memset(dp,-1,sizeof(dp));
    printf("%d\n", (fast(26,M)-dfs(1,0)+mod)%mod);
}

洛谷 P-3311 数数

原题地址

这题跟上面那题几乎一样，不过这是真正的数位DP，2333

题意：给出一个字典，求不大于N的且包含字典中任意字符串的正整数有多少个。

思路：

当然是建好AC自动机
然后在上面跑数位DP呀，别踩坑点就行
比如前缀0不能跑

题目描述

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

输入格式

输入的第一行包含整数N。接下来一行一个整数M，表示S中元素的数量。接下来M行，每行一个数字串，表示S中的一个元素。

输出格式

输出一行一个整数，表示答案模109+7的值。

输入输出样例

输入
20
3
2
3
14
输出
14

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e4+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn];
int trie[maxn][10], fail[maxn], cnt, ed[maxn];
ll ans;

void insert() {
    int len=strlen(s), p=0;
    for(int i=0; i<len; ++i) {
        int k=s[i]-'0';
        if(!trie[p][k]) trie[p][k]=++cnt;
        p=trie[p][k];
    }
    ed[p]=1;
}

void build() {
    queue<int> q;
    for(int i=0; i<10; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(int i=0; i<10; ++i) {
            if(trie[now][i]) {
                fail[trie[now][i]]=trie[fail[now]][i];
                if(ed[trie[fail[now]][i]]) ed[trie[now][i]]=1;
                q.push(trie[now][i]);
            }
            else trie[now][i]=trie[fail[now]][i];
        }
    }
}

int dp[1210][1510];
int N, tot, num[1210];

void getnum() {
    tot=strlen(s);
    for(int i=0; i<tot; ++i) num[i]=s[i]-'0';
}

int dfs(int pos, int now, int first, int f) {
    if(pos==tot) return !first;
    if(!first&&!f&&~dp[pos][now]) return dp[pos][now];
    ll ans=0;
    int up=f?num[pos]:9;
    for(int i=0; i<=up; ++i) {
        if(i) {
            if(!ed[trie[now][i]]) ans+=dfs(pos+1,trie[now][i],0,i==up&&f);
        }
        else if(!first) {
            if(!ed[trie[now][i]]) ans+=dfs(pos+1,trie[now][i],0,i==up&&f);
        }
        else ans+=dfs(pos+1,now,1,i==up&&f);
    }
    ans%=mod;
    if(!first&&!f) dp[pos][now]=(int)ans;
    return (int)ans;
}

int main() {
    //ios::sync_with_stdio(false);
    memset(dp,-1,sizeof(dp));
    scanf("%s", s);
    getnum();
    int M=read();
    for(int i=0; i<M; ++i) scanf("%s", s), insert();
    build();
    printf("%d\n", dfs(0,0,1,1));
}