bzoj2553

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

很明显看题知算法，知道这道题肯定是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 do
102     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.

View Code