题目传送门
>原文链接<

题解 :

对输入的子串建立Trie图,这样我们就可以直接在图上DP了。

  • 方程 :F[i][j]表示已经说了i个字符,在图上j点的概率。

  • 转移 :若son不是危险节点,F[i+1][son]+=F[i][j]\times temp 其中temp是说son这个字符的概率,等于\frac{1}{alphabet}

  • son是危险节点,那么走到它相当于匹配了一次禁忌串,可以统计答案再从根重新开始走

    由于匹配到每个危险节点的答案贡献都是1,那么期望可以通过计算概率和得到。

    但是len太大了,O(len)跑不下来。

    因为这是一张图,每次都走一步,我们可以考虑用邻接矩阵做矩阵乘法优化。

    每乘一次边表相当于走了一步。

    这样为了方便统计答案,我们需要建立一个虚拟汇点,每次向根转移的同时也转移到它。最后读取答案的时候直接读取它即可。

    注意本题卡精度,必须用long \;double,尤其是temp = 1/alphabet中的1也要强制转long\;double

代码 :

#include <queue>#include <cstdio>#include <cstring>using namespace std;#define f3 long doubleconst int N = 110;char s[N];int n, len, alphabet;struct Mat { f3 a[N][N]; Mat() {memset(a, 0, sizeof a);} f3* operator [] (int cur) {return a[cur];} void operator *= (Mat &b) { Mat c; for(int i = 0; i <= n; i ++ ) for(int j = 0; j <= n; j ++ ) for(int k = 0; k <= n; k ++ ) c[i][j] += a[i][k]*b[k][j]; *this = c; } Mat operator ^ (int y) { Mat I; for(int i = 0; i <= n; i ++ ) I[i][i] = 1; for(;y;y>>=1, *this *= *this) if(y&1) I *= *this; return I; }}f;struct Aho_Corasick_Automaton { int cnt, ch[N][26], fail[N]; bool flg[N], vis[N]; queue<int> q; void insert() { int p = 0; for(int i = 1; s[i]; i ++ ) { int &son = ch[p][s[i]-'a']; if(!son) son = ++cnt; p = son; } flg[p] = 1; } void getFail() { for(int i = 0; i < alphabet; i ++ ) if(ch[0][i]) q.push(ch[0][i]); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 0; i < alphabet; i ++ ) { if(ch[u][i]) fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]); else ch[u][i] = ch[fail[u]][i]; } flg[u] |= flg[fail[u]]; } } void getF() { f3 tmp = (f3)1.0/alphabet; q.push(0); vis[0] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 0; i < alphabet; i ++ ) { if(!vis[ch[u][i]]) vis[ch[u][i]] = 1, q.push(ch[u][i]); if( flg[ch[u][i]]) f[u][n] += tmp, f[u][0] += tmp; else f[u][ch[u][i]] += tmp; } } f[n][n] = 1; }}Trie;int main() { scanf("%d%d%d", &n, &len, &alphabet); for(int i = 1; i <= n; i ++ ) { scanf("%s", s+1); Trie.insert(); } n = Trie.cnt+1; Trie.getFail(); Trie.getF(); printf("%.7f\n", (double)(f^len).a[0][n]); getchar(), getchar();}