显然自动机上高斯消元
根据AC自动机上的转移可以列出一系列方程
但这个样的方程解出来全0是一组解
说明有线性组合的情况
考虑除非没人能赢,否则每个人赢的概率和为1
那么我们只要把原来的第一个方程换成这个即可
var ans,d:array[..] of double;
a:array[..,..] of double;
w,q,f:array[..] of longint;
trie:array[..,..] of longint;
v:array[..] of boolean;
j,k,i,n,m,l,x,y,t:longint;
s:string; procedure swap(var a,b:double);
var c:double;
begin
c:=a;
a:=b;
b:=c;
end; procedure ac;
var h,r,x,y,i:longint;
begin
h:=;
r:=;
for i:= to m do
if trie[,i]> then
begin
inc(r);
q[r]:=trie[,i];
end; while h<=r do
begin
x:=q[h];
for i:= to m do
if trie[x,i]> then
begin
y:=trie[x,i];
inc(r);
q[r]:=y;
j:=f[x];
while (j>) and (trie[j,i]=) do j:=f[j];
f[y]:=trie[j,i];
end;
inc(h);
end;
end; procedure gauss;
var i,j,k,p,u:longint;
c:double;
begin
u:=;
for i:= to t do
begin
p:=u;
for j:=u+ to t do
if abs(a[j,i])>abs(a[p,i]) then p:=j; if (p=u) and (a[p,i]=) then continue;
if p<>u then
begin
for j:= to t+ do
swap(a[u,j],a[p,j]);
end;
for j:=u+ to t do
if a[j,i]<> then
begin
c:=a[j,i]/a[u,i];
for k:= to t+ do
a[j,k]:=a[j,k]-a[u,k]*c;
end;
inc(u);
end;
for i:=t downto do
begin
if a[i,i]= then continue;
for j:=i+ to t do
a[i,t+]:=a[i,t+]-ans[j]*a[i,j];
ans[i]:=a[i,t+]/a[i,i];
end;
end; begin
readln(n,l,m);
for i:= to m do
begin
readln(x,y);
d[i]:=x/y;
end;
for i:= to n do
begin
readln(s);
j:=;
for k:= to l do
begin
x:=ord(s[k])-;
if trie[j,x]= then
begin
inc(t);
trie[j,x]:=t;
end;
j:=trie[j,x];
end;
w[i]:=j;
v[j]:=true;
end;
ac;
for i:= to t do
begin
a[i,i]:=-;
if not v[i] then
begin
for k:= to m do
begin
j:=i;
while (j>) and (trie[j,k]=) do j:=f[j];
a[trie[j,k],i]:=a[trie[j,k],i]+d[k];
end;
end;
end;
for i:= to t do
if not v[i] then a[,i]:= else a[,i]:=;
a[,t+]:=;
gauss;
for i:= to n do
if (ans[w[i]]>) and (ans[w[i]]<=) then
writeln(ans[w[i]]::)
else writeln('0.00');
end.