集训队论文《浅谈生成函数在掷骰子问题上的应用》 阅读笔记
集训队论文《浅谈生成函数在掷骰子问题上的应用》 阅读笔记
概率生成函数
对于随机非负离散变量 \(x\) ，它的概率生成函数是 \(F(z)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)z^i\end{aligned}\)。
有性质：
\(F(1)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)=1\end{aligned}\)。
\(F'(1)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot i=E(x)\end{aligned}\)。
\(E(x^{\underline{k}})=F^{(k)}(1)\) （ \(x\) 的 \(k\) 阶下降幂）。
\(x\) 的方差 \(=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot (i-E(x))^2\end{aligned}=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot i^2-2P(x=i)\cdot i\cdot E(x)+P(x=i)\cdot E^2(x)\end{aligned}\)
\(=E(x^2)-2E^2(x)+E^2(x)=E(x^2)-E^2(x)=E(x^{\underline{2}})+E(x)-E^2(x)=F''(1)+F'(1)-(F'(1))^2\)
CTSC2006 歌唱王国
给定序列 \(A_{1.. n}\)。
求从一个空序列每次放 \([1,m]\) 随机，第一次出现 \(A\) 的期望长度。
设当前对应 \(\text{kmp}\) 位置为 \(i\) ，每次都可以转移一下：
\(F(n)=0\)
\(F(i)=\frac{\sum_{j=1}^m F(nxt_{i,j})}{m}+1\)
\(nxt\) 非拓扑关系，且无法枚举 \(1..m\)。
考虑每次 \(\text{kmp}\) 合法匹配指针最多位移一位，令 \(G(i)\) 为匹配变为 \(i+1\) 的期望次数，则 \(G(i)=\sum_{j=1}^{m}\sum_{k=nxt_{i,j}}^{i} G(k)\)。
设 \(sum_i=\sum_1^{i}G(i)\) ，依次求出 \([1,n-1]\) 所有的 \(G(i)\)。
并不需要知道真的 \(nxt\) 数组，只需要知道 \(-sum_{nxt_{i,j}-1}\) ，每次从 \(fail_i\) 转移过来，改变一个位置的值，可以 \(O(1)\) 完成计算，即可做到 \(O(n)\)。