【题解】[CTSC2006]歌唱王国

[CTSC2006]歌唱王国

$T$ 组询问，每次给出长度为 $m$ 的序列 $a$。
现在你将生成一个随机序列，字符集为 $1-n$，每次在序列末尾等概率随机一个数。当 $a$ 成为了随机序列中的一个连续子序列则结束随机。
询问随机序列的期望长度。
$1\le T\le 50, 1\le n,m\le 10^5$。

$\text{Solution:}$

$\text{PGF}$ 入门题。

设 $F(z)$ 表示一个离散随机变量 $X(X\in \mathbb{N})$ 的概率生成函数，若令 $P_{X=i}$ 表示随机变量 $X$ 取 $i$ 的概率，那么：

$$ F(z)=\sum_{i} P_{X=i}z^i $$

与大部分其他生成函数不同的一点是，$\text{PGF}$ 虽然是生成函数，但是其特殊点值实际上是有意义的。例如：

$$ F(1)=\sum_{i} P_{X=i}=1 $$

同时，不难发现该随机变量的期望是：

$$ \sum_{i} P_{X=i}\times i $$

这个东西可以直接对 $\text{PGF}$ 进行一次求导：

$$ F'(z)=\sum_{i=1} i\times P_{X=i}z^{i-1} $$

那么 $E(X)=F'(1)$，实际上就是在用带入点值消去 $z$。而 $F^{(k)}(1)=E(X^{\underline{k}})$，也就是 $F$ 的 $k$ 阶导可以求 $X$ 的下降幂的期望值。

考虑本题。令 $f_n$ 表示恰好在序列长为 $n$ 时结束的概率，那么其 $\text{PGF}$ $F(z)$ 的一阶导 $z=1$ 处的点值就是序列长度的期望；$g_n$ 表示序列长为 $n$ 时仍未结束的概率，其 $\text{PGF}$ 为 $G(z)$。

$g_n$ 实际就是序列长度 $>n$ 的概率，那么考虑建立两者之间的关系：不妨考虑序列长度 $\ge n$ 的概率，显然是 $f_n+g_n=g_{n-1}$，因为 $\text{len}>n-1\leftrightarrow \text{len}\ge n$。

因此有等式：

$$ F(z)+G(z)=zG(z)+1 $$

也就是把 $G$ 进行一个平移，让 $g_{n-1}$ 到第 $n$ 项的位置。考虑到要求 $F'(1)$，所以先两边求导：

$$ F'(z)+G'(z)=zG'(z)+G(z) $$

那么：

$$ F'(1)+G'(1)=G'(1)+G(1) $$

这里又因为 $z=1$ 而巧妙地将一个 $z$ 消掉了。因此 $F'(1)=G(1)$，只需要求 $G(1)$ 即可。

考虑从另一个角度建立 $F,G$ 的关系，考虑什么时候会结束。如果我们要求必定结束，但是不一定是第一次出现就结束，那么有这样一个柿子：

$$ G(z)\times \Big(\dfrac{z}{n}\Big)^m $$

也就是在当前序列后面直接接上一个需要匹配的串。这一定能保证加数结束。但是我们可能算多了，因为可能在填满这个串之前就已经完成匹配了。接着又是一个 $\text{trick}$：

此处不直接考虑删除 $G$ 中的贡献，而是对 $F$ 进行类似的变换，得到具有同样意义的 $\text{PGF}$。

那就对 $F$ 做类似的东西。不难发现，若 $G$ 中提前结束了，那么在结束之后填多的东西恰好是匹配串的一个 $\text{border}$。不妨设 $s_i=[\text{1-i 是匹配串的一个 border}]$，那么有：

$$ G(z)\times \Big(\dfrac{z}{n}\Big)^m=\sum_{i=1}^m s_i F(z)\Big(\dfrac{z}{n}\Big)^{m-i} $$

也就是枚举在哪里就提前结束了，然后把后面多填的填上。这样等式两边就具有了一样的意义。

我们要求 $G(1)$，这柿子随便推推就得到：

$$ E(\text{len})=F'(1)=G(1)=\sum_{i=1}^m s_in^i $$

先做一遍 $\text{kmp}$ 求 $\text{border}$，然后快速幂即可。

$\text{Summary:}$

咕咕咕