0.前言
上周刷 GF 题的时候看到了这个东西，感觉好麻烦就懒得做，结果集训出到了硬币游戏加强版就 GG 了……
所以突击了一下知识点，㗅整理在这里。
1.[CTSC2006]歌唱王国
我们先来简单介绍一下 PGF，其实它是一种特殊的 OGF，只不过系数是一个概率：对于离散随机变量 (X)，它的 PGF 为 (sumlimits_{i=0}^{infty}P(X=i)x^i)。
然后就可以一眼看出它有一些平凡的性质，比如带入 (x=1) 会得到 (1) 或者求导得到期望的 OGF 之类的。
做 PGF 题的常用套路是设两个：(F(x)) 表示在第某个数字结束的概率，(G(x)) 表示在某个数字未结束的概率。
那么对于这题我们容易发现 (xG(x)+1=F(x)+G(x))，这是因为新加一个数字游戏可能结束也可能未结束。
我们还可以强制让它结束：(G(x)left(dfrac1nx
ight)^m=sumlimits_{i=1}^m[pre_i=suf_i]F(x)left(dfrac1nx
ight)^{m-i})，这个式子看起来很恐怖，但它的意义是很明显的。
我们现在强制让它结束，那么有可能还没加到 (m) 长度就提前结束了，假设加到第 (i) 个位置结束，容易发现 (pre_i) 一定是一个 border，然后把没加的补上去。
对于这个题要求歌唱时间的期望，我们求导得到 (F'(1)=G(1))，再对第二个式子化简得 (G(1)=sumlimits_{i=1}^m[pre_i=suf_i]F(1)n^i)，然后就可以直接算了。
2.[SDOI2017]硬币游戏
我们直接加强上一题，现在有多个名字，求概率。
为了方便我们设 (P(S)) 是一个串 (S) 出现的概率。
仿照上例，我们有 (xG(x)+1=sum F_i(x)+G(x)) 和 (G(x)P(S_i)x^m=sumlimits_{j=1}^nsumlimits_{k=1}^m[pre_{i,k}=suf_{j,k}]F_j(x)P(S_i[k+1,m])x^{m-k})。
然后代入得 (G(1)=sumlimits_{j=1}^nsumlimits_{k=1}^m[pre_{i,k}=suf_{j,k}]F_j(1)dfrac1{P(S_i[1,k])})，我们发现这是一个跟 (F_i(1)) 和 (G(1)) 有关的 (n+1) 元 (n) 次方程……欸等等，这好像解不了啊？
但是别忘了概率的基本性质，就是 (sum F_i(1)=1)，这样就可以直接解方程了。
原题只有两种颜色，是弱化版。
3.没了
好水啊……似乎也没有什么别的例题了……