【tyvj1519】博彩游戏

2014年5月11日1,9280

背景 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 [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

数据分布:
第1个点~第10个点,每个点5分;
第11个点~第15个点,每个点10分。

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

题解
此题n的范围为100
ac自动机+dp,做法和bzoj1030相同。。