[GD_SGOI 数字贴吧]AC自动机上的动态规划、高精度

【题目】

提交文件：num.pas/.cpp

输入文件：num.in

输出文件：num.out

 

在百度贴吧里输入关键词，就可以进入相应的贴吧参与该话题的讨论。然而，有一些关键词是不能作为贴吧名称的。我们把这些关键词称为敏感词。

如果一个字符串的任何子串（包括本身）都不是敏感词，那么这个字符串才可以作为贴吧名称。

有一些贴吧是直接用数字作为贴吧名称的。例如：“0”、“1”、“100”、“0123456789”。然而，数字里面也有敏感词。如果“00”是敏感词，则包含连续2个“0”的数字都不得作为贴吧名称。

你的任务是统计一下一共有多少个数字可以作为贴吧名称。

 

输入格式：

第一行是Ｎ和Ｍ，表示贴吧名称的最大长度为Ｎ（N≤63），一共有M（Ｍ≤10）个数字是敏感词。

以下M行每行一个数字，长度都不超过5。

 

输出格式：

输出可以作为贴吧名称的数字个数。

 

输入样例:

3 10

2

3

4

5

6

7

8

9

10

11

 

输出样例：

6

 

样例解释：

只有“0”、“1”、“00”、“01”、“000”、“001”可以作为贴吧名称。

【算法分析】
很容易发现。就是AC自动机dp，貌似又叫DFA？
然后对给出的串建立AC自动机。
于是F[i][j]表示已建立的串长度为i，在自动机中的j状态，所能有的方案数。
然后转移的话，就是在自动机的每个状态那里，加一个0~9的字符，然后给“转移以后的状态”加上当前这个状态的方案数。（加法原理。。。）
但是“推出方案数”的状态不能是一个串的结尾，因为按题意不能匹配！

最后的答案就是所有F[i][j]之和。当然，j不能是一个串的结尾。
最后由于这题实在太不厚道，还要用高进度写F[i][j]。。。
太猥琐了。。。
【CODE】
#include #include #include const int N=55;
int n,m,tot,Q[N];
struct Trie_t{int son[10];int Final,next;}Tr[N];
int F[70][55][101];
char str[N];

void Insert(){
int L=strlen(str);
int p=1;
for (int i=0;i if (Tr[p].son[str[i]-‘0’]) p=Tr[p].son[str[i]-‘0’];
else{
tot++;
Tr[p].son[str[i]-‘0’]=tot;
p=tot;
}
Tr[p].Final++;
}

void init(){
tot=1;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
scanf("%s",str);
Insert();
}
}

void makenext(){
int head=0,tail=1;
Q[1]=1;
while (head!=tail){
head++;
int &p=Q[head];
if (Tr[Tr[p].next].Final) Tr[p].Final=1;
for (int c=0;c<10;c++)
if (Tr[p].son){
int q=Tr[p].next;
while (q && !Tr[q].son) q=Tr[q].next;
if (q) Tr[Tr[p].son].next=Tr[q].son;
else Tr[Tr[p].son].next=1;
Q[++tail]=Tr[p].son;
}
}
}

void plus(int *A,int *B){
for (int i=1;i<=100;i++) A[i]+=B[i];
for (int i=100;i>1;i–){
A[i-1]+=A[i]/10;
A[i]%=10;
}
}

void output(int *A){
int i,j;
for (i=1;i<=100;i++)
if (A[i]){
for (j=i;j<=100;j++) printf("%d",A[j]);
printf("n");
return;
}
printf("0n");
}

void dp(){
memset(F,0,sizeof(F));
F[0][1][100]=1;
for (int L=0;L for (int i=1;i<=tot;i++) if (!Tr[i].Final)
for (int j=0;j<10;j++){
int p=i;
while (p && !Tr[p].son[j]) p=Tr[p].next;
if (!p) plus(F[L+1][1],F[L][i]);
else plus(F[L+1][Tr[p].son[j]],F[L][i]);
}
int ans[101];
memset(ans,0,sizeof(ans));
for (int i=1;i<=n;i++)
for (int j=1;j<=tot;j++) if (!Tr[j].Final)
plus(ans,F[i][j]);
output(ans);
}

int main(){
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
init();
makenext();
dp();
}