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[..,..] of longint;

     f:array[..,..] of int64;

     fail,q:array[..] of longint;

     flag:array[..] of boolean;

     s:string;

 procedure insert;

  var i,now:longint;

  begin

  readln(s);now:=;

  for i:= to length(s) do

   begin

   j:=ord(s[i])-ord('');

   if a[now,j]= 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:=;t:=;q[]:=;fail[]:=;

  while h<t do

   begin

   inc(h);now:=q[h];

   for i:= to r do

    begin

    if a[now,i]= then continue;

    k:=fail[now];

    while a[k,i]= 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:=;

  readln(n,m,r);

  for i:= to r do a[,i]:=;

  for i:= to m do insert;

  acmatch;

  end;

 procedure dp(x:longint);

  var i,j,k:longint;

  begin

  for i:= to tot do

   begin

   if (flag[i]) or (f[x-,i]=) then continue;

   for j:= to r do

    begin

    k:=i;

    while a[k,j]= do k:=fail[k];

    inc(f[x,a[k,j]],f[x-,i]);

    end;

   end;

  end;

 procedure main;

  begin

  ans2:=;

  f[,]:=;

  for i:= to n do ans2:=ans2*r;

  for i:= to n do dp(i);

  for i:= to tot do

   if not(flag[i]) then inc(ans1,f[n,i]);

  writeln((ans2-ans1)/ans2::);

  end;

 begin

  assign(input,'input.txt');assign(output,'output.txt');

  reset(input);rewrite(output);

  init;

  main;

  close(input);close(output);

 end.                               

tyvj1519博彩游戏的相关教程结束。