参考18年集训队论文《浅谈生成函数在掷骰子问题上的应用》。
一个随机变量\(X\)的PGF定义为 :
\[F(z)=\sum_{i=0}^{\infty}\mathrm{P}(X=i)z^i\]当然需要满足\(X\geq 0\)，不然这就不是一个带项式了。
容易发现
\[\mathrm{E}(X)=\sum_{i=0}^{\infty}i\cdot\mathrm{P}(X=i)=F^\prime(1)\]所以我们如果解出了\(F\)，容易求得\(\mathrm{E}(X)\)。
还有一个方差的是
\[\begin{aligned} \mathrm{Var}(X)&=\mathrm{E}(X^2)-\mathrm{E}(x)^2\\ \mathrm{E}(X^2)&=\sum_{i=0}^{\infty}i^2\cdot\mathrm{P}(X=i)=\sum_{i=0}^{\infty}i(i-1)\cdot\mathrm{P}(X=i)+\sum_{i=0}^{\infty}i\cdot\mathrm{P}(X=i)=F^{\prime\prime}(1)+F^\prime(1) \end{aligned}\]这个不是很常用，不过很好记。同时它还告诉我们如何计算\(E(X^k)\)，也就是用斯特林数展成下降幂。
题意 : 有一个字符串\(s\)，现在你要搞一个字符串\(t\)，每次随机往后加一个字符，当\(s\)在\(t\)中出现就停下，求\(t\)的期望长度。\(s\)长度为\(m\)，字符集大小是\(n\)。
Solution : 我们考虑对\(s\)建立自动机。设\(f_i\)表示长度是\(i\)的概率，\(g_i\)表示长度达到\(i\)并且还没停下的概率，特别地，\(f_0=0,g_0=1\)。那么答案就是\(F^\prime(1)\)。
考虑从一个没停下的串后面加一个字符会发生什么。最简单的结论是，要么会停下来，要么不会停下来，所以我们有
\[zG(z)+1=F(z)+G(z)\]那个\(1\)是边界情况，也就是啥也没有的情况。当然这个还不足以解出这俩鬼东西。
再考虑一个更强的结论，任何一个\(t\)后面加上一个\(s\)就一定会停止，所以可以写出
\[\frac{1}{n^m}z^mG(z)=F(z)\]但是这个有点问题，因为\(t\)有可能已经匹配了\(s\)前面的一部分，所以只需要加不到\(n\)个就可以了。
具体地，如果现在已经匹配了\(s\)的长为\(k\)的前缀，那么接下来只需要\(m-k\)次就可以结束了。发现好像需要对这个相等情况进行容斥!这不好。
这里有一步非常妙，我们考虑硬加了一个\(s\)而不管能不能提前结束之后，\(t\)的最后是什么情况。注意这里是不管已经匹配了什么都加一个\(s\)上去。
假设在加之前\(t\)的长度是\(p\)，并且末尾已经匹配了长度至少为\(k\)的\(s\)的前缀，并且只加了\(m-k\)步就结束了，你会发现\(t[p-k+1,p+m-k]=t[p,p+m-1]=s\)。
观察\(t[p,p+m-k]\)，它同时是\(t[p-k+1,p+m-k]=s\)的一个后缀和\(t[p,p+m-1]=s\)的一个前缀，所以它就是\(s\)的一个border。同时我们知道如果\(s[1,i]\)是border，那么\(s[i+1,m]=s[1,m-i]\)也是border，换句话说我们加之前匹配的也是一个border，并且只有匹配一个border才可能提前结束。同时我们硬加一个\(s\)上去，相当于结束之后又多加了\(k\)个字符。
设\(a_i\)表示\(s[1,i]\)是不是一个border，特别地有\(a_0=0\)。那么枚举已经匹配的长度\(k\)，我们得到
\[\begin{aligned} \frac{1}{n^m}z^mG(z)&=\sum_{k=0}^{m-1}a_{m-k}\frac{1}{n^{k}}z^{k}F(z)\\ &=\sum_{k=1}^{m}a_k\frac{1}{n^{m-k}}z^{m-k}F(z) \end{aligned}\]这是两个方程了!让我们来做一些代数运算。
考虑如果要求\(F^\prime(1)\)，显然是第一个式子更容易求导，因此我们先试一试。两边求导并代入\(z=1\) :
\[\begin{aligned} zG(z)+1&=F(z)+G(z)\\ G(z)+zG^\prime(z)&=F^\prime(z)+G^\prime(z)\\ G(1)+G^\prime(1)&=F^\prime(1)+G^\prime(1)\\ F^\prime(1)&=G(1) \end{aligned}\]问题变成求\(G(1)\)，看起来很有成效啊!接下来我们处理第二个式子 :
\[\begin{aligned} \frac{1}{n^m}z^mG(z)=\sum_{k=1}^{m}a_k\frac{1}{n^{m-k}}z^{m-k}F(z)\\ \frac{1}{n^m}G(1)=\sum_{k=1}^{m}a_k\frac{1}{n^{m-k}}F(1)\\ G(1)=\sum_{k=1}^{m}a_kn^k \end{aligned}\]就做完了。谢谢朋友们!（
容易看出一个ACAM上随机游走的模型，但是随机游走只能做期望?考虑因为每个终点要么不经过要么经过一次，那么经过它的概率应该等于经过它的期望次数。所以我们得到了一个\(O(n^3m^3)\)的优秀算法，可以拿到40pts!实际上SDOI2017现场最高分也是40pts。
终点看起来没法删去，我们考虑把中间那些没啥用的点都合成一个点，它的状态是所有没有结束的局面。设每个同学赢的概率是\(f_i\)，你发现没法转移/cy
考虑类似上题的做法，我们增加一维，设\(f_{i,j}\)表示第\(i\)个同学在\(j\)轮赢了的概率，设\(g_i\)表示\(i\)轮过去还是没人赢的概率，那么求的就是所有\(F_i(1)\)。首先还是可以写出
\[zG(z)+1=G(z)+\sum F_i(z)\]然后考虑分别给每个人加一下他的串，并考虑在加完之前提前结束的概率，这里需要枚举每个人看他如何提前结束。对于第\(i\)个人，可以写出下面的式子 :
\[\frac{1}{2^m}z^mG(z)=\sum_{j=1}^n\sum_{k=1}^m\left[s_i[1,k]=s_j[m-k+1,m]\right]\frac{1}{2^{m-k}}z^{m-k}F_j(z)\]代入\(z=1\)，就得到\(n+1\)个方程，高斯消元求解即可。
呃这些方程是什么?
\[\begin{aligned} 1&=\sum F_i(1)\\ G(1)&=\sum_{j=1}^n\sum_{k=1}^m\left[s_i[1,k]=s_j[m-k+1,m]\right]2^{k}F_j(1) \end{aligned}\]这题的高消非常鬼，如果每次都选取最大的当作主元，精度要求会达到1000位的级别从而导致巨大的浮点误差，你会全输出0!如果直接选当前行当主元，就可以过题。这主要是因为\(2^{300}\)已经爆了精度。