题解 P4569 [BJWC2011]禁忌

· · 题解

题目传送门。

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

在我的 cnblog 内查看。

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 <bits/stdc++.h>
using namespace std;

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using db = double;
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 <int> q;
    for(int i=0;i<al;i++)if(son[0][i])q.push(son[0][i]);
    while(!q.empty()){
        int t=q.front(); q.pop();
        for(int i=0;i<al;i++)
            if(son[t][i])q.push(son[t][i]),fa[son[t][i]]=son[fa[t]][i];
            else son[t][i]=son[fa[t]][i];
        ed[t]|=ed[fa[t]];
    }
}
struct mat{
    ld a[N][N];
    friend mat operator * (mat x,mat y){
        mat z; mem(z.a,0);
        for(int i=0;i<=sz;i++)
            for(int j=0;j<=sz;j++)
                for(int k=0;k<=sz;k++)
                    z.a[i][j]+=x.a[i][k]*y.a[k][j];
        return z;
    }
}base,ans;

int n,len;
int main(){
    cin>>n>>len>>al;
    for(int i=0;i<n;i++){
        string s;
        cin>>s,ins(s);
    } build();
    for(int i=0;i<=sz;i++)
        for(int j=0;j<al;j++){
            int p=son[i][j];
            if(ed[p])base.a[i][0]+=1.0/al,base.a[i][sz+1]+=1.0/al;
            else base.a[i][p]+=1.0/al;
        }
    sz++,ans.a[0][0]=base.a[sz][sz]=1;
    while(len){
        if(len&1)ans=ans*base;
        base=base*base,len>>=1;
    } printf("%.10Lf\n",ans.a[0][sz]);
    return 0;
}