【JSOI2007】文本生成器

Source and Judge

JSOI2007 文本生成器
Bzoj1030
Luogu4052

Problem

【Description】
给出一些单词和文本固定长度,求所有满足此长度的,
包含至少一个单词的文本的数量,对10007取模。
【Input】
第一行两个数表示单词数量n和文本长度m。
接下来每行一个字符串表示单词。
【Output】
答案。
【Limited conditions】
单词数n<=60
所有字符串长度、m<=100
【Sample input】
2 2
A
B
【Sample output】
100
【Sample explanation】

Record

3h

Analysis

请先思考后再展开

最先,也是最重要的一点:把答案容斥,转化为更容易计算的,不包含任何单词的文本数量,然后用总量26^m-数量即是答案。
而这种包含与否的关系,很容易联想到多串匹配,那当然少不了AC自动机。
接下来呢?

我们所要求的,就是跳m次,没有跳到任何一个【单词结尾节点】的方案数。
但是考虑这样一种情况:只有单词a和bbabbb,m=3,然后我们跳到第三层的a,然后以为没有经过任何单词,就累计了答案。然而,不难发现其实我们还是包含了单词a。所以必须确保其任何后缀都不是单词的结尾。网上大部分人都是暴力跳fail去验证,然而其实可以在计算fail的时候,顺便递推过来,能节省时间(注意要用与运算),因为此时的bfs,fail的深度一定比x小。

一种直观的想法就是直接dfs跳,然后套一个记忆化。。。
那既然如此不如直接dp?反正是等效的吧

那我们就可以愉快地dp啦
你可以想象一个长度为m的任意字符串在ac机上面跳来跳去
所以我们可以在任何时刻任意追加字符
然而这样空间消耗非常大
但是不难发现,对于一个不在ac机上面的点,其接下来的拓展性与自己无关(fail=0),所以是等价于根节点0的,所以为了方便和节省空间,可以把空节点也设为0.
一开始连模板都打错了qwq

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=110;
const int MOD=10007;
//*******************全局定义*******************
char s[MAXN];
int Mod(int x) {return (x%MOD+MOD)%MOD;}
//*******************实现*******************
struct Trie
{
int ch[26];
bool ed;
int fail;
void clear()
{
memset(ch,0,sizeof(ch));
fail=ed=0;
}
}a[MAXN*60];
int cnt=0;
void add()
{
scanf("%s",s+1);
int ln=strlen(s+1);
int now=0;
for(int i=1;i<=ln;i++)
{
int t=s[i]-'A';
if(!a[now].ch[t]) a[now].ch[t]=++cnt,a[cnt].clear();
now=a[now].ch[t];
}
a[now].ed=1;
}
queue<int> q;
void getfail()
{
q.push(0);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=0;i<26;i++)
{
int son=a[x].ch[i];
if(!son) continue;
if(x==0) a[son].fail=0;//debug 模板都打错了
else
{
int p=a[x].fail;
while(p>0 and !a[p].ch[i]) p=a[p].fail;
a[son].fail=a[p].ch[i];
a[son].ed|=a[a[son].fail].ed;//debug 与运算
}
q.push(son);
}
}
}
int ans=0,m;
int f[MAXN][MAXN*60];
bool v[MAXN][MAXN*60];
typedef pair<int,int> pp;
queue<pp> q2;
void solve()
{
f[0][0]=v[0][0]=1;
q2.push(pp(0,0));
while(!q2.empty())
{
int now=q2.front().first,sp=q2.front().second;q2.pop();
if(sp==m) {ans=Mod(ans+f[sp][now]);continue;}
for(int i=0;i<26;i++)
{
int tmp=now;
while(tmp>0 and !a[tmp].ch[i]) tmp=a[tmp].fail;
int son=a[tmp].ch[i];
if(!a[son].ed)
{
f[sp+1][son]=Mod(f[sp+1][son]+f[sp][now]);
if(!v[sp+1][son])
{
v[sp+1][son]=1;
q2.push(pp(son,sp+1));
}
}
}
}
}
//*******************主函数*******************
int main()
{
int n;scanf("%d%d",&n,&m);
a[0].clear();
while(n--) add();
getfail();
solve();
int fm=1;for(int i=1;i<=m;i++) fm=Mod(fm*26);
printf("%d",Mod(fm-ans));
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/文本生成器.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%