题目链接

<h2>题目描述</h2>

题目大意：给你前 $alphabet$ 个小写字母组成的字符集，以及 $n$ 个单词，定义一个串 s 的禁忌值为 $\sum_{i} [s[i] == Taboo[i]]$，其中 $Taboo[i]$ 是第 $i$ 个单词（禁忌值也就是找到一种分割字符串的方法 使得出现这N个字符串的次数最多的次数）。现在给定一个长度 $len$，求随机一个用字符集生成的长度为 $len$ 的串的禁忌值的期望。

其中 $n \leq 5,len \leq 10^9,1 \leq alphabet \leq 26$，保证给出的每个单词长度不超过 $15$。

<h2>题解</h2>

考虑当我们已经知道了这个随机出来的串是什么的时候，如何求这个串的禁忌值。显然我们可以把所有的单词都投影到串上，就变成了一个选出一些两两不交的线段使得选取的数量尽量多，这个直接贪心就可以。我们考虑这个过程就相当于建立 AC 自动机后，在自动机上走，碰到一个结束节点就返回根节点并且答案累加 $1$。（因为先被匹配到的串肯定是左端点靠前，尽量短的串）

然后我们考虑另一个问题：给定一个图，求从 $u$ 到 $v$ 恰好经过 m 条边的路径条数 $n \leq 10^2,m \leq 10^9$。

考虑我们处理出这个图的邻接矩阵，然后发现每一次多经过一条边相当于对于每一对点枚举中界点来使得路径长度正好 $+1$，也就是
$$ans = \sum_{i=1}^n a[u][i]*a[i][v]$$
然后这十分像矩阵乘法，于是就是将邻接矩阵自乘 $m$ 了 QAQ。

回到这个题上，我们发现求期望只需要将 $a[i][j]$ 表示 $i$ 一步到 $j$ 的步数，只要处理出这个然后一波矩阵快速幂就好了。

考虑我们设一个终点，然后每走到 AC 自动机的一个节点就设当前节点到所有儿子的一步期望为 $\frac{1}{alphabet}$，走到一个带有结束标志的节点就设定其到根节点和终点的期望为 $\frac{1}{alphabet}$，就可以了。

要注意这题中如果 AC 自动机上一个节点的 fail 指针指向的节点是结束节点，那么他也应当是一个结束节点，并且矩阵要初始化终点节点一步到自己的期望步数为 $1$。

最后 貌似听别人说这题卡精度？long double 保平安。。。。。。

<h2>代码</h2>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define LD long double
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 6;
const int MAXC = 100+5;
int n,len,alphabet;
bool vis[MAXN];

struct Matrix{
    LD aMAXC;
    Matrix operator * (const Matrix &t) const {
        Matrix ans;
        FOR(i,0,MAXC-1){
            FOR(j,0,MAXC-1){
                ans.ai = 0.0;
                FOR(k,0,MAXC-1){
                    ans.ai += ai*t.ak;
                }
            }
        }
        return ans;
    }

    Matrix operator ^ (int n) const {
        Matrix res,a = *this;
        FOR(i,0,MAXC-1) FOR(j,0,MAXC-1) res.ai = (i == j);
        while(n){
            if(n & 1) res = res*a;
            a = a*a;
            n >>= 1;
        }
        return res;
    }
}a,b;

const int MAXL = MAXN*16000;

namespace AC{
    int tag[MAXL],chMAXL,cnt = 1,fail[MAXL];

    inline void insert(char str[]){
        int len = strlen(str+1),v = 1;
        FOR(i,1,len){
            int x = str[i]-'a';
            if(!chv) chv = ++cnt;
            v = chv;
        }
        tag[v] = 1;
    }

    inline void build(){
        std::queue<int> q;
        q.push(1);
        while(!q.empty()){
            int v = q.front();q.pop();
            tag[v] |= tag[fail[v]];
            int pos;
            FOR(i,0,alphabet-1){
                pos = fail[v];
                while(pos && !chpos) pos = fail[pos];
                if(chv){
                    failch[v] = pos ? chpos : 1;
                    q.push(chv);
                }
                else chv = pos ? chpos : 1;
            }
        }
    }

    inline void calc(){
        std::queue<int> q;
        q.push(1);vis[1] = true;
        while(!q.empty()){
            int v = q.front();q.pop();
            FOR(i,0,alphabet-1){
                if(!visch[v]) visch[v] = 1,q.push(chv);
                if(tagch[v]){
                    a.av += (LD)1.0/alphabet;
                    a.av += (LD)1.0/alphabet;
                }
                else a.av[i]] += (LD)1.0/alphabet;
            }
        }
        a.acnt+1 = 1;
    }
}

char strMAXN;

int main(){
    scanf("%d%d%d",&n,&len,&alphabet);
    FOR(i,1,n) scanf("%s",str[i]+1),AC::insert(str[i]);
    AC::build();AC::calc();
    b = a^len;
    printf("%.6Lfn",b.a1);
    return 0;
}