题目传送门

前置知识

AC 自动机 | 矩阵加速递推

解法

• 对于一段固定的文本串，由于重叠的模式串不对伤害产生贡献，故考虑贪心，每碰到出现一个模式串将其分为一段，最终这个文本串的伤害就是划分次数。
• 类似 luogu P3193 [HNOI2008] GT考试 ，令 \(f_{i,j}\) 表示前 \(i\) 个字符，当前运行到 \(AC\) 自动机的 \(j\) 状态时受到的概率。状态转移方程为 \(\begin{cases}f_{i+1,k}=\sum\limits_{j=0}^{tot} [k \in Son(j)] \times [vis_{k}=0] \times f_{i,j} \times \frac{1}{alphabet} & k \ne 0 \\ f_{i+1,0}=\sum\limits_{j=0}^{tot}\sum\limits_{k=0}^{tot}[k \in Son(j)] \times [vis_{k}=1] \times f_{i,j} \times \frac{1}{alphabet} \end{cases}\)，其中 \(vis_{k}\) 表示 \(AC\) 自动机上是否存在以 \(k\) 结尾的字符串。另外，若 \(vis_{k}=1\)，则可能会受到一次伤害，有 \(ans=ans+f_{i,j} \times \frac{1}{alphabet}\)。
• 因 \(len \le 10^{9}\)，故需要矩阵加速递推。
• 令 \(F_{t}=\begin{bmatrix} f_{t,0} & f_{t,1} & f_{t,2} & \dots & f_{t,tot} & \sum\limits_{i=1}^{t-1}f_{i,0} \end{bmatrix}\)，容易有 \(\begin{aligned} F_{t} &=\begin{bmatrix} f_{t,0} & f_{t,1} & f_{t,2} & \dots & f_{t,tot} & ans_{t} \end{bmatrix} \\ &=\begin{bmatrix} f_{t-1,0} & f_{t-1,1} & f_{t-1,2} & \dots & f_{t-1,tot} & ans_{t-1} \end{bmatrix} \times \begin{bmatrix} \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(0)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(0)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(1)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(1)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(2)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(2)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(2)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(tot)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(tot)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(tot)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} \\ 0 & 0 & 0 & \dots & 0 & 1 \end{bmatrix} \\ &=\begin{bmatrix} f_{t-2,0} & f_{t-2,1} & f_{t-2,2} & \dots & f_{t-2,tot} & ans_{t-2} \end{bmatrix} \times \begin{bmatrix} \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(0)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(0)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(1)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(1)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(2)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(2)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(2)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(tot)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(tot)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(tot)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} \\ 0 & 0 & 0 & \dots & 0 & 1 \end{bmatrix}^{2} \\ &=\begin{bmatrix} f_{t-3,0} & f_{t-3,1} & f_{t-3,2} & \dots & f_{t-3,tot} & ans_{t-1} \end{bmatrix} \times \begin{bmatrix} \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(0)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(0)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(1)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(1)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(2)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(2)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(2)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(tot)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(tot)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(tot)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} \\ 0 & 0 & 0 & \dots & 0 & 1 \end{bmatrix}^{3} \\ &=\dots \\ &=\begin{bmatrix} f_{0,0} & f_{0,1} & f_{0,2} & \dots & f_{0,tot} & ans_{0} \end{bmatrix} \times \begin{bmatrix} \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(0)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(0)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(1)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(1)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(2)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(2)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(2)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(tot)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(tot)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(tot)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} \\ 0 & 0 & 0 & \dots & 0 & 1 \end{bmatrix}^{t} \\ &=\begin{bmatrix} 1 & 0 & 0 & \dots & 0 & 0 \end{bmatrix} \times \begin{bmatrix} \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(0)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(0)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(1)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(1)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(2)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(2)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(2)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(tot)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(tot)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(tot)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} \\ 0 & 0 & 0 & \dots & 0 & 1 \end{bmatrix}^{t} \\ &=F_{0} \times \begin{bmatrix} \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(0)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(0)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(0)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(0)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(1)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(1)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(1)] \times [vis_{i}=1]}{alphabet} \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(2)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(2)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(2)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(2)] \times [vis_{i}=1]}{alphabet} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} & \frac{[1 \in Son(tot)] \times [vis_{1}=0]}{alphabet} & \frac{[2 \in Son(tot)] \times [vis_{2}=0]}{alphabet} & \dots & \frac{[tot \in Son(tot)] \times [vis_{tot}=0]}{alphabet} & \sum\limits_{i=0}^{tot}\frac{[i \in Son(tot)] \times [vis_{i}=1]}{alphabet} \\ 0 & 0 & 0 & \dots & 0 & 1 \end{bmatrix}^{t} \end{aligned}\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct Matrix
{
	long double ma[80][80];
	Matrix()
	{
		memset(ma,0,sizeof(ma));
	}
}f,a;
int trie[80][30],fail[80],vis[80],tot=0;
char s[80];
Matrix mul(Matrix a,Matrix b,int n,int m,int k)
{
	Matrix c;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			for(int h=1;h<=m;h++)
			{
				c.ma[i][j]=c.ma[i][j]+a.ma[i][h]*b.ma[h][j];
			}
		}
	}
	return c;
}
Matrix qpow(Matrix a,int b,int n)
{
	Matrix ans;
	for(int i=1;i<=n;i++)
	{
		ans.ma[i][i]=1.0;
	}
	while(b>0)
	{
		if(b&1)
		{
			ans=mul(ans,a,n,n,n);
		}
		b>>=1;
		a=mul(a,a,n,n,n);
	}
	return ans;
}
int val(char x)
{
	return x-'a'+1;
}
void insert(char s[],int len)
{
	int x=0,i;
	for(i=1;i<=len;i++)
	{
		if(trie[x][val(s[i])]==0)
		{
			tot++;
			trie[x][val(s[i])]=tot;
		}
		x=trie[x][val(s[i])];
	}
	vis[x]=1;
}
void build(long double alphabet)
{
	int x,i;
	queue<int>q;
	for(i=1;i<=alphabet;i++)
	{
		if(trie[0][i]!=0)
		{
			fail[trie[0][i]]=0;
			q.push(trie[0][i]);
		}
	}
	while(q.empty()==0)
	{
		x=q.front();
		q.pop();
		for(i=1;i<=alphabet;i++)
		{
			if(trie[x][i]==0)
			{
				trie[x][i]=trie[fail[x]][i];
			}
			else
			{
				fail[trie[x][i]]=trie[fail[x]][i];
				vis[trie[x][i]]|=vis[fail[trie[x][i]]];//继承标记
				q.push(trie[x][i]);
			}
		}
	}
}
int main()
{
	int b,nn,n,m,k,i,j;
	long double alphabet;
	cin>>nn>>b>>alphabet;
	for(i=1;i<=nn;i++)
	{
		cin>>(s+1);
		insert(s,strlen(s+1));
	}
	build(alphabet);
	n=1;
	m=k=tot+2;
	f.ma[1][1]=a.ma[m][m]=1;
	for(i=0;i<=tot;i++)
	{
		for(j=1;j<=alphabet;j++)
		{
			if(vis[trie[i][j]]==0)
			{
				a.ma[i+1][trie[i][j]+1]+=1.0/alphabet;
			}
			else
			{
				a.ma[i+1][1]+=1.0/alphabet;
				a.ma[i+1][m]+=1.0/alphabet;
			}
		}
	}
	printf("%.12Lf\n",mul(f,qpow(a,b,m),n,m,k).ma[1][m]);
	return 0;
}