P4569 [BJWC2011]禁忌

题目传送门。

题意简述：给出大小为 \(n\) 的字典 \(s\)。设函数 \(g(t)\) 表示 \(t\) 最多能被分割成的单词个数。等概率随机生成长度为 \(len\) 的字符串 \(T\)，求 \(E(g(t))\)。

在 Luogu 博客中查看。

hot tea. 比较像 P3193 [HNOI2008]GT考试。

& 。

首先对 \(s_i\) 建出 ACAM，然后在上面 DP。设 \(f_{i,j}\) 表示关于所有 \(T\)（\(|T|=i\) 且 \(T\) 在 ACAM 上能跑到状态 \(j\)）的一个东西。那么究竟是表示什么呢？

记 \(P=\dfrac{f_{i,j}}{a}\)；\(p\) 为 \(j\) 的所有子节点，即 \(p\in son_j\)。

错误思路：如果 \(f_{i,j}\) 单纯表示字符串 \(T\) 的 “概率”（即 \(\dfrac{num(T)}{a^i}\)），那么转移与统计答案就是：如果 \(p\) 是终止节点，将 \(ans\) 加上 \(P\)；同时将所有 \(f_{i+1,p}\) 加上 \(P\)。不错，如果 \(g(T)\) 表示的是所有单词 \(s_i\) 在 \(T\) 中出现次数之和，那么这样是没错的，可惜不是，因为会有重复计算，即若字典 \(s=\{\texttt{ab,bc}\}\)，那么 \(T=\{\texttt{abc}\}\) 会算入两次贡献（样例中也有提到这种情况）。

正确思路：注意到这个 "最多" 有点麻烦，不过还是有处理的办法：如果 \(p\) 是一个终止节点，那么在下传概率的时候，将 \(f_{i+1,0}\)（而不是 \(f_{i+1,p}\)）加上 \(P\)。如果成功匹配一个单词，就必须从头开始匹配。

注意到 \(\sum |s_i|\) 很小，只有 \(75\)。这也意味着 \(j\) 的范围只有 \(75\)。因此，用矩阵快速幂加速 DP 即可，别忘了在矩阵中留个位置记录 \(ans\)。

总时间复杂度 \(\mathcal{O}((\sum |s_i|)^3\log len)\)。

/*
    Powered by C++11.
    Author : Alex_Wei.
*/

#include 
using namespace std;

//#pragma GCC optimize(3)
//#define int long long

using ld = long double;

const int N=77;
const int S=26;

int sz,al,son[N][S],fa[N],ed[N];
void ins(string s){
    int p=0;
    for(char it:s){
        if(!son[p][it-'a'])son[p][it-'a']=++sz;
        p=son[p][it-'a'];
    } ed[p]=1;
}
void build(){
    queue  q;
    for(int i=0;i>n>>len>>al;
    for(int i=0;i>s,ins(s);
    } build();
    for(int i=0;i<=sz;i++)
        for(int j=0;j>=1;
    } printf("%.10Lf\n",ans.a[0][sz]);
    return 0;
}