Bzoj1030 [jsoi2007]文本生成器

AC自动机上跑DP

Posted by yjjr's blog on February 24, 2018

标签:AC自动机,DP,容斥原理

题目

题目传送门

Description

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

该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说,生成的文章中每个字节都是完全随机的。

如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。

但是,即使按照这样的标准,使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。

ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量,以便能够成功获得v7更新版。你能帮助他吗?

Input

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

Output

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

Sample Input

2 2
A
B

Sample Output

100  

题意

给定多个模式串和M

求一个长度为M的新串,不与任何一个模式串匹配的方案数

分析

因为有多个模式串,先建立AC自动机

然后DP

f[i][j]表示当长度为i时匹配到j节点时的情况数

根据point节点转移,相当于在Trie树上DP

用容斥原理考虑否定(不可读)的情况,然后用总的方案数m^26减去否定的情况

否定的情况就是

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=6e3+6,mod=1e4+7;
int trie[maxn][27],point[maxn],que[maxn<<2],f[106][maxn];
char st[maxn];int n,m,id=1,ans1,ans2=1;
bool danger[maxn];
void insert(){
	int now=1,k,len=strlen(st+1);
	rep(i,1,len){
		k=st[i]-'A'+1;
		if(!trie[now][k])trie[now][k]=++id;
		now=trie[now][k];
	}
	danger[now]=1;
}
void acmach(){
	int head=0,tail=1,now;
	que[0]=1;point[1]=0;
	while(head<tail){
		now=que[head++];
		rep(i,1,26){
			if(!trie[now][i])continue;
			int k=point[now];while(!trie[k][i])k=point[k];
			point[trie[now][i]]=trie[k][i];que[tail++]=trie[now][i];
			if(danger[trie[k][i]])danger[trie[now][i]]=1;
		}
	}
}
void dp(int x){
	rep(i,1,id){
		if(danger[i]||!f[x-1][i])continue;
		rep(j,1,26){
			int k=i;
			while(!trie[k][j])k=point[k];
			f[x][trie[k][j]]=(f[x][trie[k][j]]+f[x-1][i])%mod;
		}
	}
}
int main()
{
	n=read(),m=read();
	rep(i,1,26)trie[0][i]=1;
	rep(i,1,n)scanf("%s",st+1),insert();
	acmach();
	f[0][1]=1;
	rep(i,1,m)dp(i);
	rep(i,1,m)ans2=(ans2*26)%mod;
	rep(i,1,id)
		if(!danger[i])ans1=(ans1+f[m][i])%mod;
	cout<<(ans2-ans1+mod)%mod<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr