题解 P4548 【[CTSC2006]歌唱王国】

2019-07-25 20:31:54


以下统一规定 $n$ 为字符集大小, $m$ 为名字长度。

设 $f_i$ 表示长度为 $i$ 时结束的概率, $g_i$ 表示长度为 $i$ 时没有结束的概率。

设 $f_i$ 的概率生成函数为 $F(x)$ , $g_i$ 的概率生成函数为 $G(x)$ 。

根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。

分析一下可以列出这样一个式子

$$\displaystyle xG(x)+1=F(x)+G(x)\qquad\cdots\ (1)$$

这个式子的意义是加一个字符后可能结束也可能没有结束。感觉是废话,但是真的可以列一个式子

再分析一下可以列出这样一个式子

$$\displaystyle G(x)\cdot\left(\frac{1}{n}x\right)^m=\sum_{i=1}^ma_i\cdot F(x)\cdot\left(\frac{1}{n}x\right)^{m-i}\qquad\cdots\ (2)$$

这里的 $a_i$ 表示 $[1,i]$ 是否是名字的一个 border 。

这个式子的意义是在一个未结束的序列后加上名字一定会结束,但是有可能在没有到 $m$ 个字符时就结束了,此时添加的序列是名字的一个 border 。

把 $(1)$ 求导可以得到

$$\displaystyle\begin{aligned}xG'(x)+G(x)&=F'(x)+G'(x)\\F'(x)&=(x-1)G'(x)+G(x)\qquad\cdots\ (3)\end{aligned}$$

把 $x=1$ 代入 $(3)$ 可以得到

$$\displaystyle F'(x)=G(x)\qquad\cdots\ (4)$$

把 $x=1$ 代入 $(2)$ 可以得到

$$\displaystyle\begin{aligned}G(1)\cdot\left(\frac{1}{n}\right)^m&=\sum_{i=1}^ma_i\cdot F(1)\cdot\left(\frac{1}{n}\right)^{m-i}\\G(1)&=\sum_{i=1}^ma_i\cdot F(1)\cdot n^i\\G(1)&=\sum_{i=1}^ma_i\cdot n^i\qquad\cdots\ (5)\end{aligned}$$

联立 $(4)(5)$ 可以得到

$$\displaystyle F'(1)=\sum_{i=1}^ma_i\cdot n^i$$

用 KMP / hash 求出 $a_i$ 即可。

代码