本文共 4907 字，大约阅读时间需要 16 分钟。

题目

思路

感谢提供了思路。我不生产思考，我只是智慧结晶的搬运工。

首先，按照一般的做法，设 $f_x$ 表示长度为 $x$ 时成功匹配的概率；$g_x$ 表示长度为 $x$ 时没有成功匹配（长度超过 $x$ 时完成匹配）的概率。然后就发现做不动了。

怎么办呢？使用船新操作：概率生成函数！名字听着玄乎，其实不好用，而且难点不在这上面。

我们将 $F(x)={\sum }_{i=0}^{+\infty }{E}_i{x}^i$ 称为概率生成函数。其中 $E_i$ 表示检测值为 $i$ 的概率。

将 $x=1$ 代入，得到 $F(1)={\sum }_{i=0}^{+\infty }{E}_i=1$ （万川东到海，概率和为一）。

对 $F$ 求导，得到 $F^{\prime }(x)={\sum }_{i=1}^{+\infty }i{E}_i{x}^{i-1}$ ；于是将 $x=1$ 代入，得到 $F^{\prime }(1)={\sum }_{i=1}^{+\infty }i{E}_i=e$ （即原本要求的期望值）。

说了这么多，我们回到这道题，考虑这两个生成函数：

• $f$ 的生成函数 $F(x)={\sum }_{i=0}^{+\infty }{f}_i{x}^i$
• $g$ 的生成函数 $G(x)={\sum }_{i=0}^{+\infty }{g}_i{x}^i$

我们要找他们之间的关系，可以找 $f$ 和 $g$ 之间的关系。

关系一

$$g_i=f_{i+1}+g_{i+1}$$

这是当然咯，长度为 $i$ 时没有匹配，那就是长度为 $i+1$ 时匹配，或者比 $i+1$ 更长的时候匹配。

我们试着用生成函数的形式写出来：

$$\begin{array}{rl}F(x)& =f_0+f_{1}x+f_2{x}^2+\cdots +f_n{x}^n+\cdots \\ G(x)& =g_0+g_{1}x+g_2{x}^2+\cdots +g_n{x}^n+\cdots \\ xG(x)& =g_{0}x+g_1{x}^2+\cdots +g_{n-1}{x}^n+\cdots \end{array}$$

加之 $f_0=0,g_0=1$ ，显然，$$xG(x)=F(x)+G(x)-1\text{\hspace{1em}(1)}$$

尽管 $(1)$ 式目前没有什么用，等会儿我们会看到它的功力。虽然那个结论不用生成函数也能证。

关系二（不易发现）

用 $L$ 表示原字符串的长度，$m$ 表示字符集（生成时是每次在 $[1,m]$ 中随机一个整数）大小，则

$${\left(\frac{1}{m}\right)}^L\cdot g_x=\sum _{i=1}^L{a}_i{\left(\frac{1}{m}\right)}^{L-i}\cdot f_{x+i}$$

$a_i$ 表示，原字符串的前 $i$ 位和后 $i$ 位是否相同。相同为 $1$ ，否则为 $0$ 。即，原字符串是否有一个长度为 $i$ 的 $\mathrm{b}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}$ 。为啥有这个式子成立呢？

首先，$f$ 表示的已经匹配的字符串，一定是 以原字符串结尾。也就是说，最后 $L$ 个字符一定就是原字符串。而且，去掉最后一个字符，一定没有完成匹配。

看右边的式子。$a_i=1$ 时才会累加，这就代表着原字符串前 $i$ 个字符与后 $i$ 个字符相同。而 $f_{i+x}$ 就是以原字符串结尾的。所以 $f_{i+x}$ 的后 $i$ 位，恰好就是原字符串的后 $i$ 位，与原字符串的前 $i$ 位相同。此时，在末尾接上一截剩下的 $L-i$ 位，最后 $L$ 位就恰好匹配了。$\mathrm{I}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{s}$ ，我们完成了一个长度为 $x+L$ 的匹配于尾端，但是只能保证前 $x$ 位没有匹配。

对于左式，很简单，对于一个长度为 $x$ 的、尚未完成匹配的字符串，我在后面暴力接入了一个原字符串。两式都代表一个长度为 $x+L$ 的已经匹配的字符串，故相等。

其实，右式就是在枚举：将原字符串的前 $i$ 位接到最后，就已经完成了匹配。

我们再用生成函数的方法写出来：

$$\begin{array}{rl}{\left(\frac{x}{m}\right)}^{L}G(x)& =\sum _{i=0}^{+\infty }{\left(\frac{1}{m}\right)}^L{g}_i{x}^{i+L}\\ F(x)\sum _{i=1}^L{a}_i{\left(\frac{x}{m}\right)}^{L-i}& =\sum _{i=0}^{+\infty }{x}^{i+L}\sum _{j=1}^L{a}_j{\left(\frac{1}{m}\right)}^{L-j}{f}_{i+j}\end{array}$$

你可能会问，下面那个等式是怎么搞出来的？可以考虑 $x^{i+L}$ 的系数由什么组成。假设左式的求和中的 $a_j(\frac{x}{m}{)}^{L-j}$ 为之提供了贡献，由于其次数是 $L-j$ ，所以原本 $F(x)$ 中是 $x^{i+j}$ 这一项与之相乘。故 $F(x)$ 的系数是 $f_{i+j}$ ，求和中的系数是 $a_j(\frac{1}{m}{)}^{L-j}$ ，相乘即可。

仔细观察，得到结论：$${\left(\frac{x}{m}\right)}^{L}G(x)=F(x)\sum _{i=1}^L{a}_i{\left(\frac{x}{m}\right)}^{L-i}\text{\hspace{1em}(2)}$$

嗯，好像差不多，该进行体力工作了：暴力解！

对 $(1)$ 式两边求导，有$$x{G}^{\prime }(x)+G(x)=F^{\prime }(x)+G^{\prime }(x)$$

导数基本姿势 $[f(x)g(x){]}^{\prime }=f^{\prime }(x)g(x)+f(x)g^{\prime }(x)$ 应该是人尽皆知的吧？

然后你可以移项，得到$$F^{\prime }(x)=(x-1)G^{\prime }(x)+G(x)$$

$F^{\prime }(x)$ 鸟用没有，我们想知道的是什么？在 $x=1$ 处的取值。答案就是 $F^{\prime }(1)$ 嘛。我们试试：

$$F^{\prime }(1)=(1-1)G^{\prime }(1)+G(1)=G(1)$$

这告诉我们，$G(1)$ 就是答案！虽然这个结论不用生成函数也挺显然的。

$(2)$ 式还没有使用呢。我们拿出来，发现 $G(x)$ 也鸟用没有——我们需要 $G(1)$ 。我们再试一次：

$${\left(\frac{1}{m}\right)}^{L}G(1)=F(1)\sum _{i=1}^L{a}_i{\left(\frac{1}{m}\right)}^{L-i}$$

哦，对了，我一来就说了，$F(1)=1$ 恒成立。代入如何？

$$G(1)=\sum _{i=1}^L{a}_i\times m^i$$

任务完成。$a_i$ 这种东西，哈希呗！（虽然 $\mathtt{k}\mathtt{m}\mathtt{p}$ 可能更好打。）

代码

看了看题解，并不长的样子。然而我还是不想打了。

实在想要代码，去题解区搞一份噻！

后记

$\mathsf{K}\mathsf{n}\mathsf{o}\mathsf{w}\mathsf{N}\mathsf{a}\mathsf{m}\mathsf{e}\mathsf{B}\mathsf{l}\mathsf{o}\mathsf{g}\mathsf{e}\mathsf{r}$ 在另一道类似的题目中，试图在后方加入一个长度为 $n-1$ 的串，然而总是差一项。我也百思不得其解。进行了充分的思考之后，我意识到：加上长度为 $n-1$ 的串对 $g_0$ 不适用。所以那种方法求出来的值会小 $1$ 。