题解 P4569 【[BJWC2011]禁忌】
lzx2005
·
·
题解
【算法分析】
算法一：（对于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个节点的禁忌伤害概率值。
当$\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，其他细节见代码注释。
【参考程序】
```cpp
#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;
}
```