[51nod 1444]打字的猴子

一、题目

二、解法

考虑$dp$dp，设$E[i]$E[i]为已经成功匹配到了$i$i，想要匹配到$n$n的期望，那么答案就是$E[0]$E[0]，考虑多匹配一个字符后的影响，我们用$trans$trans来描述它，转移如下：
$E[x]=\frac{1}{k}\sum_{i=1}^k E[trans[x][i]]+1$E[x]=k1​i=1∑k​E[trans[x][i]]+1由于$trans$trans并不是一定比$x$x小，需要高斯消元，时间复杂度$O(n^3)$O(n3)。

---

考虑优化，考虑$trans$trans的性质，很重要的一点是$x$x和$fail[x]$fail[x]的$trans$trans除了$s[x+1]$s[x+1]这一项（可以匹配），其它的值都是一模一样的，我们可以据此列出恒等式：
$E[x]-E[fail[x]]=E[trans[x][s[x+1]]]\times\frac{1}{k}-E[trans[fail[x]][s[x+1]]\times\frac{1}{k}$E[x]−E[fail[x]]=E[trans[x][s[x+1]]]×k1​−E[trans[fail[x]][s[x+1]]×k1​$E[x]-E[fail[x]]=E[x+1]\times\frac{1}{k}-E[fail[x+1]]\times\frac{1}{k}$E[x]−E[fail[x]]=E[x+1]×k1​−E[fail[x+1]]×k1​我们设$G(x)=E(x)-E(fail[x])$G(x)=E(x)−E(fail[x])，那么上式可以化简成：
$G(x)=G(x+1)\times \frac{1}{k}$G(x)=G(x+1)×k1​$G$G其实是有边界的，$G(1)=E(1)-E(0)=-k$G(1)=E(1)−E(0)=−k，那么$G(x)=-k^x$G(x)=−kx，于是$G(n)=E(n)-E(fail(n))=-k^n$G(n)=E(n)−E(fail(n))=−kn，由于$E(n)=0$E(n)=0，所以$E(fail[n])=k^n$E(fail[n])=kn，$E(fail[fail[n]])=k^n+k^{fail[n]}$E(fail[fail[n]])=kn+kfail[n]，以此类推即可得到答案$E(0)$E(0)。

咕咕咕