Description：

$n$ 个长度为 $l$ 的串， $m$ 个字符，每次随机生成一位，对于每个串求出这个串在这个生成序列中是第一次出现的概率。

$1\leqslant n,m,l\leqslant 10$

Solution：

建 $AC$ 自动机，然后设 $f[i]$ 表示没有经过任何结束点走到 $i$ 的概率： $$ f[i]=\sum_{k\xrightarrow{c}i}f[k]\times p[c] $$ 于是我们得到了 $n$ 个方程，高斯消元解方程组即可，时间复杂度 $O((nm)^3)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 110

int n,l,m;

double p[MAXN];

char c[MAXN];

struct node

{

	int tr[12],fail;

	bool tag;

}t[MAXN];

int pos[MAXN];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void insert(char c[],int id)

{

	int cur = root;

	int l = strlen(c + 1);

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

	{

		int w = c[i] - 'A' + 1;

		if(t[cur].tr[w] == 0)t[cur].tr[w] = newnode();

		cur = t[cur].tr[w];

	}

	t[cur].tag = true;

	pos[id] = cur;

	return;

}

double g[MAXN][MAXN];

double res[MAXN];

int main()

{

	scanf("%d%d%d",&n,&l,&m);

	int a,b;

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

	{

		scanf("%d%d",&a,&b);

		p[i] = 1.0 * a / b;

	}

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

	{

		scanf("%s",c + 1);

		insert(c,i);

	}

	queue<int> q;

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

	{

		if(t[root].tr[i] != 0)

		{

			t[t[root].tr[i]].fail = root;

			q.push(t[root].tr[i]);

		}

	}

	while(!q.empty())

	{

		int k = q.front();q.pop();

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

		{

			if(t[k].tr[i] != 0)

			{

				t[t[k].tr[i]].fail = t[t[k].fail].tr[i];

				q.push(t[k].tr[i]);

			}

			else

			{

				t[k].tr[i] = t[t[k].fail].tr[i];

			}

		}

	}

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

	{

		g[i][i] -= 1;

		if(t[i].tag)continue;

		for(int j = 1;j <= m;++j)g[t[i].tr[j]][i] += p[j];

	}

	g[0][ptr + 1] = -1;

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

	{

		bool tag = false;

		for(int j = i;j <= ptr;++j)

		{

			if(fabs(g[j][i]) > 1e-8)

			{

				swap(g[i],g[j]);

				tag = true;

				break;

			}

		}

		if(!tag)continue;

		for(int j = i + 1;j <= ptr;++j)

		{

			double delta = g[j][i] / g[i][i];

			for(int k = i;k <= ptr + 1;++k)

			{

				g[j][k] = g[j][k] - g[i][k] * delta;

			}

		}

	}

	for(int i = ptr;i >= 0;--i)

	{

		res[i] = g[i][ptr + 1] / g[i][i];

		for(int j = i - 1;j >= 0;--j)g[j][ptr + 1] -= g[j][i] * res[i];

	}

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

	{

		if(fabs(res[pos[i]]) < 1e-3)puts("0.00");

		else printf("%.2lf\n",res[pos[i]]);

	} 

	return 0;

}