诶这题洛谷居然没有？？？

题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1444

题解: 我见到主要有三种做法。

一是矩阵乘法。设\(dp[t][i]\)表示时间\(t\)之后在AC自动机\(i\)节点的概率，那么转移是一个矩阵乘法的形式，构造转移矩阵\(f\), 如果\(u\)是某个串的结尾点，则\(f[u][u]=1,f[u][v]=0 (v\ne u)\), 否则直接按概率搞。

然后这个矩阵的\(t\)次幂就可以得到\(t\)时刻后在每个点的概率。但是这题时间到无穷。

可以感觉到随着\(t\)的增加不匹配任何串的概率不断减小，\(t\)无穷大时达到0. 而题目精度要求并不高，所以如果我们能够使得\(t\)非常大而精度误差被控制在要求范围内，就做完了。

非常粗略地估算一下，\(t=10^{12}\)时矩阵每一项的精度误差远小于\(1\times 10^{-4}\) (别问我怎么算的，我放缩的幅度太大了，实际的界应该小于\(10^{12}\))

所以把矩阵自乘\(40\)次就完了。时间复杂度\(O(n^6\times 40)\) (所有范围为\(10\)的参数不加以区分)

二是高斯消元。

对于任何节点\(u\), 其概率等于所有入边的概率乘上其字母权值之和，然后这样可以列出\(siz\) (AC自动机大小)个方程，但是如果这么解的话得到的答案是所有未知数全等于\(0\), 然后就把根的方程去掉，改成所有结束节点的概率之和等于\(1\), 解出来就A掉了……

完全不理解他是要干什么，拿某些题解代码一看，发现有的点解出来概率都是\(2\)……

到最后终于翻到一篇详细解释这个做法的题解: 如果设概率直接拿方程列上会全得\(0\), 原来这个未知数设的并非概率，而是经过该点的期望次数(对于结束节点期望次数就等于概率)，然后\(x_0\) (\(0\)为根)等于所有入边概率之和\(+1\) (因为上来先到一次), 其余节点等于所有入边概率之和即可解。也可以不要根的那个等式，换成所有结束节点期望次数之和为\(1\), 应该是等价的。(天哪看了一晚上终于看懂了……)

时间复杂度\(O(n^6)\)

据说还有一个枚举每个人的\(O(n^7)\)做法……大佬们太强了我啥都看不懂啊

三是矩阵求逆，这个貌似(对我来说)还好理解一些……

矩阵第\(i\)行第\(j\)列是从\(i\)转移到\(j\)的概率，结尾节点的这一行全部为0. 这个和做法一的区别就是结尾节点转移到自己的概率不是\(1\), 那么原来要求\(T^{+\inf}\)现在就变成要求\(T+T^2+T^3+...+T^{+\inf}\), 这个矩阵元素都小于\(1\)应该收敛的，那么直接求\(T\times (1-T)^{-1}\)即可。

时间复杂度\(O(n^6)\)

代码

做法一

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

const int N = 10;

const int S = 10;

const int LEN = 10;

const int SIZ = 100;

const int LGM = 40;

int son[SIZ+3][S+3];

int fail[SIZ+3];

int que[SIZ+3];

double p[N+3];

int id[N+3];

char a[N+3][LEN+3];

int n,len,s,siz;

struct Matrix

{

	double a[SIZ+3][SIZ+3];

	Matrix operator *(const Matrix &arg) const

	{

		Matrix ret;

		for(int i=0; i<=siz; i++) for(int j=0; j<=siz; j++) ret.a[i][j] = 0.0;

		for(int i=0; i<=siz; i++)

		{

			for(int k=0; k<=siz; k++)

			{

				for(int j=0; j<=siz; j++)

				{

					ret.a[i][j] += a[i][k]*arg.a[k][j];

				}

			}

		}

		return ret;

	}

} f;

void insertstr(char str[],int sid)

{

	int u = 0;

	for(int i=1; i<=len; i++)

	{

		if(son[u][str[i]]==0) {siz++; son[u][str[i]] = siz;}

		u = son[u][str[i]];

	}

	id[sid] = u;

}

void buildACA()

{

	int head = 1,tail = 0;

	for(int i=1; i<=s; i++)

	{

		if(son[0][i]) {tail++; que[tail] = son[0][i];}

		fail[son[0][i]] = 0;

	}

	while(head<=tail)

	{

		int u = que[head]; head++;

		for(int i=1; i<=s; i++)

		{

			if(son[u][i]) {fail[son[u][i]] = son[fail[u]][i]; tail++; que[tail] = son[u][i];}

			else {son[u][i] = son[fail[u]][i];}

		}

	}

}

int main()

{

	scanf("%d%d%d",&n,&len,&s);

	for(int i=1; i<=s; i++)

	{

		double x,y; scanf("%lf%lf",&x,&y); p[i] = x/y;

	}

	for(int i=1; i<=n; i++)

	{

		scanf("%s",a[i]+1); for(int j=1; j<=len; j++) a[i][j]-=64;

		insertstr(a[i],i);

	}

	buildACA();

	for(int u=0; u<=siz; u++)

	{

		for(int i=1; i<=s; i++)

		{

			int v = son[u][i];

			f.a[u][v] += p[i];

		}

	}

	for(int i=1; i<=n; i++)

	{

		int u = id[i];

		for(int j=0; j<=siz; j++) f.a[u][j] = (u==j) ? 1.0 : 0.0;

	}

	for(int i=1; i<=LGM; i++)

	{

		f = f*f;

	}

	for(int i=1; i<=n; i++) printf("%.2lf\n",f.a[0][id[i]]);

	return 0;

}