洛谷P4052 [JSOI2007]文本生成器

2024-03-22 18:08:10

题目描述

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

该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。也就是说，生成的文章中每个字符都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 s 包含单词 t，当且仅当单词 t 是文章 s 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器 v6 版所生成的文章也是几乎完全不可读的。ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中，可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？

答案对 \(10^4+7\) 取模。

输入格式

第一行有两个整数，分别表示使用者了解的单词总数 n 和生成的文章长度 m。

接下来 n 行，每行一个字符串 \(s\)，表示一个使用者了解的单词。

输出格式

输出一行一个整数表示答案对 \(10^4+7\) 取模的结果。

输入输出样例

输入 #1

2 2
A
B

输出 #1

Solution

利用容斥，可读文本数量=总数-不可读文本数量，总数为 \(26^m\)，所以只需要求出不可读文本数量，即长度为 \(m\) 且不含任意输入单词的字符串的数量。

可以用 \(DP\) 求解，先建出单词的AC自动机，令 \(f_{i-1,j}\) 表示串长为 \(i-1\)，在AC自动机上匹配到编号为 \(j\) 的节点的不可读文本数量。

如果 \(j\) 的儿子 \(trie_{j,k}\) 是不可读的节点，就可以从 \((i-1,j)\) 转移到 \((i,trie_{j,k})\)

\(f_{i,trie_{j,k}}=(f_{i,trie_{j,k}}+f_{i-1,j}) \bmod p\)

判断一个节点是否可读，可以在求 \(fail\) 指针的时候一起求。

最后答案为 \(26^m-f_{m,i}\) (\(i\) 为AC自动机上的所有点）

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

const int N=6010;
const int P=1e4+7;

char s[N];
int trie[N][30],tot,val[N];
int f[110][N];
 
void ins(char s[])
{
	int len=strlen(s),c=0;
	for(int i=0;i<len;i++)
	{
		int n=s[i]-'A';
		if(!trie[c][n]) trie[c][n]=++tot;
		c=trie[c][n];
	}
	val[c]=true;
}

queue<int>que;
int fail[N];
void build()
{
	for(int i=0;i<26;i++)
		if(trie[0][i]) que.push(trie[0][i]);
	while(!que.empty())
	{
		int c=que.front();
		que.pop();
		for(int i=0;i<26;i++)
		{
			if(trie[c][i]) fail[trie[c][i]]=trie[fail[c]][i],val[trie[c][i]]|=val[fail[trie[c][i]]],que.push(trie[c][i]);
			else trie[c][i]=trie[fail[c]][i];
		}
	}
}

int qpow(int a,int b)
{
	int res=1;
	a%=P;
	while(b)
	{
		if(b&1) res=res*a%P;
		a=a*a%P;
		b>>=1;
	}
	return res;
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		ins(s);
	}
	build();
	f[0][0]=1;
	for(int i=1;i<=m;i++)
		for(int j=0;j<=tot;j++)
			for(int k=0;k<26;k++)
				if(!val[trie[j][k]])
					f[i][trie[j][k]]=(f[i][trie[j][k]]+f[i-1][j])%P;
	int ans=qpow(26,m);
	for(int i=0;i<=tot;i++)
		ans=(ans-f[m][i]+P)%P;
	printf("%d\n",ans);
	return 0;
}

码农公寓