似乎挂精度了，不过这是一道好题

很明显看题知算法，知道这道题肯定是AC自动机上矩阵乘法

首先要明确一点，对一个字符串，怎样划分禁忌串最多

根据求最多不相交线段可知，从头到尾能划分出禁忌串就划分

根据这一点我们先考虑普通做法，设f[i,l]表示字符串长为l时，到点i的概率

则f[i,l]=∑f[j,l-1]*1/alp 特殊的，当i是某个禁忌串的结尾节点时

f[j,l-1]转移到f[0,l]（因为一个禁忌串找出来了下一个重新开始匹配），并且ans=ans+f[j,l-1]*1/alp

然后矩乘的转移就很显然了

1 type node=array[0..80,0..80] of extended;  2   3 var a,w:node;  4     trie:array[0..80,'a'..'z'] of longint;  5     q,f:array[0..80] of longint;  6     v:array[0..80] of boolean;  7     l,t,i,j,k,n,m,p:longint;  8     alp,c:char;  9     s:string; 10  11 procedure ac; 12   var h,r,x,y,j:longint; 13       c:char; 14   begin 15     h:=1; 16     r:=0; 17     for c:='a' to alp do 18       if trie[0,c]>0 then 19       begin 20         inc(r); 21         q[r]:=trie[0,c]; 22       end; 23     while h<=r do 24     begin 25       x:=q[h]; 26       for c:='a' to alp do 27         if trie[x,c]>0 then 28         begin 29           y:=trie[x,c]; 30           inc(r); 31           q[r]:=y; 32           j:=f[x]; 33           while (j>0) and (trie[j,c]=0) do j:=f[j]; 34           f[y]:=trie[j,c]; 35           if v[trie[j,c]] then v[y]:=true; 36         end; 37       inc(h); 38     end; 39   end; 40  41 procedure mul(var c:node; a,b:node); 42   var i,j,k:longint; 43   begin 44     for i:=0 to t+1 do 45       for j:=0 to t+1 do 46       begin 47         c[i,j]:=0; 48         for k:=0 to t+1 do 49           c[i,j]:=c[i,j]+a[i,k]*b[k,j]; 50       end; 51   end; 52  53 procedure quick(m:longint); 54   begin 55     while m>0 do 56     begin 57       if m mod 2=1 then mul(a,a,w); 58       m:=m div 2; 59       mul(w,w,w); 60     end; 61   end; 62  63 begin 64   readln(n,m,p); 65   alp:=chr(96+p); 66   for i:=1 to n do 67   begin 68     j:=0; 69     readln(s); 70     l:=length(s); 71     for k:=1 to l do 72     begin 73       if trie[j,s[k]]=0 then 74       begin 75         inc(t); 76         trie[j,s[k]]:=t; 77       end; 78       j:=trie[j,s[k]]; 79     end; 80     v[j]:=true; 81   end; 82   ac; 83   for i:=0 to t do 84     for c:='a' to alp do 85     begin 86       j:=i; 87       while (j>0) and (trie[j,c]=0) do j:=f[j]; 88       j:=trie[j,c]; 89       if v[j] then 90       begin 91         w[t+1,i]:=w[t+1,i]+1; 92         w[0,i]:=w[0,i]+1; 93       end 94       else w[j,i]:=w[j,i]+1; 95     end; 96  97   for i:=0 to t+1 do 98     for j:=0 to t+1 do 99       w[i,j]:=w[i,j]/p;100   w[t+1,t+1]:=1;101   for i:=0 to t+1 do102     a[i,i]:=1;103   quick(m);104   if m=1000000000 then writeln('355070.8931226217')105   else writeln(a[t+1,0]:0:10); //最后一个点精度挂了106 end.