自动搬运

查看原文

来自洛谷，原作者为

	lzx2005 **

搬运于2025-08-24 22:01:28，当前版本为作者最后更新于2020-02-17 16:32:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【算法分析】

算法一：（对于$40\%$的数据）：

kmp上的dp+矩阵乘法优化，可通过子任务三，得40pts。

做法类似，GT考试

https://www.luogu.com.cn/problem/P3193

http://ybt.ssoier.cn:8088/problem_show.php?pid=1646

此处不详细讲了。

算法二（对于 $30\%$ 的数据）：

本题求的是禁忌伤害的期望值。实际上，期望也就是所有可能情况的禁忌伤害的的加权平均数。不难想到，可以枚举所有可能出现的字符串，所有串的禁忌伤害和除以串的个数即为答案。对于已知的一个串，计算它的禁忌伤害，显然可以贪心：我们需要把它分成若干段，每一段包含一个禁忌串，答案即为段数。对此，我们对该串求伤害的最大值，显然要把它划分成尽量多的段。那么我们可以对禁忌串建一个AC自动机，让已知串从根节点出发进行匹配，如果遇到一个终止节点（该节点表示的字符串或其后缀为某个完整的禁忌串），则这个串的禁忌伤害加1，回到根节点继续匹配。

复杂度$O(\text{alphabet}^{\text{len}} \times len + \sum_{1}^{N}{|T_{i}|}$）可以通过子任务一，得$30pts$。

算法三（对于 $70\%$ 的数据）：

在算法二贪心计算答案的启发下，我们发现可以使用AC自动机处理本题，考虑将枚举每一个串的搜索改为期望dp。不难发现，本题可以顺推。设$\text{dp}_ {i,j}$表示长度为$i$，匹配到AC自动机上的第$j$个节点的禁忌伤害概率值。

$\forall i,j,k$（$1 \leq i\leq len,1 \leq j \leq tot,0 \leq k <alphabet$）（$tot$为AC自动机上点数）

当$\text{ch}_ {j,k}$不是终止节点时，显然有$\text{dp}_{i,\text{ch}_{j,k}} + =\text{dp}_{i - 1,j} \times \frac{1}{\text{alphabet}}$的转移方程。

否则有$\text{dp}_{i,1} + = (\text{dp}_{i - 1,j} + 1) \times\frac{1}{\text{alphabet}}$的转移方程。

初始状态全部为0，答案为$\sum_{i = 1}^{\text{len}}\sum_{j = 1}^{\text{tot}} \text{dp}_{\text{i},j}\times\text{bo}_j$。

复杂度$O(len \times tot + \sum_{1}^{N}{|T_{i}|})$可通过子任务一、二和部分子任务三得70~90pts。

算法四：

算法三中，tot在100以下，几乎可以忽略不计，超时的原因显然是$10^{9}$级别的$len$。

我们可以发现：转移方程中只在相邻的长度上转移，显然是一个tot阶递推式，可以使用矩阵乘法优化！大体思想同算法一。但由于常数项的原因，我们的转移矩阵应该是$(tot + 1) \times (tot + 1)$的。$a_{i,tot + 1}$表示当前状态到点i已经计入答案的期望值。初始矩阵，只需设为单位矩阵即可，转移矩阵构造方法如下：枚举AC自动机上每一个节点，

设当前到了第i个节点，则枚举i的每一条出边，对于点i的第k条出边

（$0 \leq k < alphabet$），若$\text{ch}_{i,k}$是终止节点，则$a_{i,tot +1} + = \frac{1}{\text{alphabet}},a_{i,tot + 1} + =\frac{1}{\text{alphabet}}$.

否则$a_{i,\text{ch}_{i,k}} + = \frac{1}{\text{alphabet}}$，特别地$a_{tot+ 1,tot + 1} = 1$保存过程中的答案，最终取$a^{\text{len}}$矩阵。

答案为$a_{1,tot + 1}$（转移len次后根节点对答案的贡献）。

使用矩阵快速幂优化，复杂度$O(\text{tot}^{3} \times\operatorname{log_2}\text{len} + tot \times \text{alphabet} +\sum_{1}^{N}{|T_{i}\ |})$,得100pts。

注意事项：

代码实现中建议全程使用long double，其他细节见代码注释。

【参考程序】

#include<bits/stdc++.h>
#define ll long long
#define re register
#define al alphabet
#define ld long double//本题精度要求较高，建议使用long double型变量
using namespace std;
inline int read()
{
	int lzx=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
	while(c>='0'&&c<='9'){lzx=lzx*10+c-'0';c=getchar();}
	return lzx*f;
}
int ch[80][26],net[80],bo[80];
int n,len,al,tot=1;
char s[101];
inline void add()//建Trie树
{
	int len=strlen(s+1),u=1;
	for(re int i=1;i<=len;i++)
	{
		int c=s[i]-'a';
		if(!ch[u][c])ch[u][c]=++tot;
		u=ch[u][c];
	}
	bo[u]=1;//点u表示的串是禁忌串
	return;
}
inline void bfs()//求next数组，建AC自动机
{
	for(re int i=0;i<26;i++)
		ch[0][i]=1;
	net[1]=0;
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		bo[u]|=bo[net[u]];//它的后缀为禁忌串，它也是禁忌串
		for(re int i=0;i<26;i++)
		{
			int v=net[u];
			while(!ch[v][i])v=net[v];
			if(ch[u][i])
			{
				q.push(ch[u][i]);
				net[ch[u][i]]=ch[v][i];
			}
			else ch[u][i]=ch[v][i];
		}
		q.pop();
	}
	return;
}
struct point 
{
	ld mapp[110][110];
	int a,b;
};//用结构体保存矩阵信息
inline void pre(point &a)
{
	for(re int i=1;i<=a.a;i++)
		for(re int j=1;j<=a.b;j++)
			a.mapp[i][j]=0.0;
	for(re int i=1;i<=tot;i++)
	{
		for(re int j=0;j<al;j++)
		{
			if(bo[ch[i][j]])
			{
				a.mapp[i][1]+=(ld)1.0/(ld)al;
				a.mapp[i][tot+1]+=(ld)1.0/(ld)al;
			}
			else a.mapp[i][ch[i][j]]+=(ld)1.0/(ld)al;
		}
	}
	return;
}//构造转移矩阵
inline point times(point a,point b)
{
	point c;c.a=c.b=a.a;
	for(re int i=1;i<=c.a;i++)
		for(re int j=1;j<=c.b;j++)
			c.mapp[i][j]=(ld)0.0;
	for(re int i=1;i<=c.a;i++)
		for(re int j=1;j<=c.b;j++)
			for(re int k=1;k<=a.b;k++)
				c.mapp[i][j]+=a.mapp[i][k]*b.mapp[k][j];
	return c;
}//两个矩阵相乘
inline point ksm(point a,int k)
{
	point res;res.a=res.b=a.a;
	for(re int i=1;i<=res.a;i++)
		for(re int j=1;j<=res.b;j++)
			res.mapp[i][j]=(ld)(i==j);
	while(k)
	{
		if(k&1)res=times(res,a);
		a=times(a,a);
		k>>=1;
	}
	return res;
}//矩阵快速幂
point a;
int main()
{
	n=read(),len=read(),al=read();
	for(re int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		add();
	}
	bfs();
	a.a=a.b=tot+1;//矩阵规格为(tot+1)×(tot+1)
	pre(a);
	a.mapp[a.a][a.b]=(ld)1.0;
	a=ksm(a,len);//求矩阵a^len
	printf("%Lf\n",a.mapp[1][tot+1]);//long double型用“%Lf”输出
	return 0;
}