tyvj1519博彩游戏

博彩游戏

From admin

背景 Background

Bob最近迷上了一个博彩游戏……

描述 Description

这个游戏的规则是这样的：
每花一块钱可以得到一个随机数R，花上N块钱就可以得到一个随机序列；
有M个序列，如果某个序列是产生的随机序列的子串，那么就中奖了，否则不中。
Bob会告诉你这M个序列，和身上有的钱的总数N，当然还有R的范围。
请你告诉Bob中奖的概率有多少？

输入格式 InputFormat

第一行三个用空格隔开的数N、M和R的范围R。
其中1<=R<=9，0<N<=60，0<M<=20000。
下面M行每行一个字符串（长度小于等于20），字符串的每一位范围在1-r之间
保证必要运算都在64位整型范围内。

输出格式 OutputFormat

一行一个实数，表示中奖的概率（保留小数点后5位小数）。

样例输入 SampleInput [复制数据]

5 1 3

 

 

 

样例输出 SampleOutput [复制数据]

0.86831

 

 

 

数据范围和注释 Hint

数据分布：
第1个点~第10个点，每个点5分；
第11个点~第15个点，每个点10分。

对于样例的解释：
随机序列一共有3^5=243个，其中包含"1"的个数为211个，则概率为211/243=0.86831

 

 

 

 

来源 Source

Bob HAN

题解：

这题和上一题差不多

代码 ：

var n,m,r,i,j,tot:longint;
    ans1,ans2:int64;
    a:array[0..400000,0..20] of longint;
    f:array[0..60,0..400000] of int64;
    fail,q:array[0..400000] of longint;
    flag:array[0..400000] of boolean;
    s:string;
procedure insert;
 var i,now:longint;
 begin
 readln(s);now:=1;
 for i:=1 to length(s) do
  begin
  j:=ord(s[i])-ord('0');
  if a[now,j]=0 then begin inc(tot);a[now,j]:=tot;end;
  now:=a[now,j];
  end;
 flag[now]:=true;
 end;
procedure acmatch;
 var h,t,i,now,k:longint;
 begin
 h:=0;t:=1;q[1]:=1;fail[1]:=0;
 while h<t do
  begin
  inc(h);now:=q[h];
  for i:=1 to r do
   begin
   if a[now,i]=0 then continue;
   k:=fail[now];
   while a[k,i]=0 do k:=fail[k];
   fail[a[now,i]]:=a[k,i];
   if flag[a[k,i]] then flag[a[now,i]]:=true;
   inc(t);q[t]:=a[now,i];
   end;
  end;
 end;
procedure init;
 begin
 tot:=1;
 readln(n,m,r);
 for i:=1 to r do a[0,i]:=1;
 for i:=1 to m do insert;
 acmatch;
 end;
procedure dp(x:longint);
 var i,j,k:longint;
 begin
 for i:=1 to tot do
  begin
  if (flag[i]) or (f[x-1,i]=0) then continue;
  for j:=1 to r do
   begin
   k:=i;
   while a[k,j]=0 do k:=fail[k];
   inc(f[x,a[k,j]],f[x-1,i]);
   end;
  end;
 end;
procedure main;
 begin
 ans2:=1;
 f[0,1]:=1;
 for i:=1 to n do ans2:=ans2*r;
 for i:=1 to n do dp(i);
 for i:=1 to tot do
  if not(flag[i]) then inc(ans1,f[n,i]);
 writeln((ans2-ans1)/ans2:0:5);
 end;
begin
 assign(input,'input.txt');assign(output,'output.txt');
 reset(input);rewrite(output);
 init;
 main;
 close(input);close(output);
end.