题目背景

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

题目描述

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

输入格式

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

输出格式

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

提示

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

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

#include <bits/stdc++.h>

using namespace std;

#define reg register

#define int long long

#define N 400005

int n, m, r;

int nxt[N][], fail[N], end[N];

int tot;

int f[][N];

int all = , ans;

char s[];

inline void Ins()

{

    int len = strlen(s);

    int now = ;

    for (reg int i =  ; i < len ; i ++)

        now = nxt[now][s[i]-''] ? nxt[now][s[i]-''] : nxt[now][s[i]-''] = ++tot;

    end[now] = ;

}

inline void AC_Match()

{

    queue <int> q;

    for (reg int i =  ; i <=  ; i ++)

        if (nxt[][i]) q.push(nxt[][i]);

    while(!q.empty())

    {

        int x = q.front();q.pop();

        for (reg int i =  ; i <= r ; i ++)

        {

            if (nxt[x][i]) fail[nxt[x][i]] = nxt[fail[x]][i], q.push(nxt[x][i]);

            else nxt[x][i] = nxt[fail[x]][i];

        }

        end[x] |= end[fail[x]];

    }

}

signed main()

{

    scanf("%lld%lld%lld", &n, &m, &r);

    for (reg int i =  ; i <= m ; i ++)

    {

        scanf("%s", s);

        Ins();

    }

    AC_Match();

    f[][] = ;

    for (reg int i =  ; i < n ; i ++)

        for (reg int x =  ; x <= tot ; x ++)

        {

            if (end[x] or !f[i][x]) continue;

            for (reg int j =  ; j <= r ; j ++)

                f[i + ][nxt[x][j]] += f[i][x];

        }

    for (reg int i =  ; i <= n ; i ++) all *= r;

    for (reg int i =  ; i <= tot ; i ++)

        if (!end[i]) ans += f[n][i];

    printf("%.5lf\n", (double)(all - ans) / (double)all);

    return ;

}