技巧
算两次；概率生成函数性质的应用
题意
给定\(\{A_i\}_{i=1}^m, A_i\in [1, n]\)(\(\sum m \le 5\times 10^6, n \le 10^5\))；生成一个序列\(\{X_i\}_{i=1}^\infty\), 其中\(X_i\)在\([1, n]\)中均匀独立随机；设随机变量\(T\)为第一个末尾位置\(t\)使得序列\(A\)在\(X\)中出现。求\(E(T)\)。
题解
首先进行一步转化，即通过拆分贡献的思想，\(E(T) = \sum\limits_{x=0}^\infty P(T>x)\)，设\(g(x) = P(T>x)\)，而\(G(z)\)为它的OGF，那么\(E(T) = G(1)\)。于是只要算\(G(1)\)即可，那么就要从\(g(x)\)入手。
接下来运用到“算两次”的技巧。考虑一个非结束的\(X\)前缀，长度为\(L\)，它后面加上\(A\)一定就结束了，但是不一定是\(m\)步以后结束，实际上在该前缀\(X\)没有终止的条件下，\(T\in [L+1, L+m]\)。接下来用两种不同的方式计算生成了\(X\)的\(L\)前缀加上\(A\)这件事(事件\(V\))的概率\(P(V)\)。
第一种方法：首先生成长度为\(L\)的前缀没终止，然后生成接下来\(m\)个恰好就是\(A\)，则\(P(V) = g(L)\cdot \frac{1}{n^m}\)。
第二种方法：首先枚举\(i\in [1, m]\)，计算\(P(T = L+i)\)；然后在这个前提下，接下来生成的\(m-i\)个数必须恰好是\(A\)的后缀，所以概率再乘上\(\frac{1}{n^{m-i}}\)；除此之外注意到，因为\(T=L+i\)，所以前\(i\)个字符一定是\(A\)的一个后缀，而为了让事件V成立，它也必须是\(A\)的一个前缀。所以只有\(A[1,i]\)是\(A\)的一个Border时才能贡献概率。
所以式子的完整版本是：
\[g(L)\cdot \frac{1}{n^m} = P(V) = \sum\limits_{i\in Border(A)} \frac{1}{n^{m-i}}\cdot P(T=L+i) \]两边同时乘以\(n^m\)得到：
\[g(L) = \sum\limits_{i\in Border(A)} n^i\cdot P(T=L+i) \]我们要求的就是\(g\)的生成函数在1处取值，所以我们用生成函数的语言改写这个式子：
\[G(z) = \sum\limits_{k=0}^\infty g(k)z^k = \sum\limits_{k=0}^\infty\sum\limits_{i\in Border(A)} n^i\cdot P(T=k+i) z^k \]然后使\(P(T=k+i)\)和\(z^k\)对齐成一个PGF的形式，得到：
\[RHS=\sum\limits_{i\in Border(A)} n^iz^{-i}\sum\limits_{k=i}^\infty P(T=k)z^k \]考虑到当\(k<i\le m\)时\(P(T=k) = 0\)，可以把后面那个求和补全到0，变成一个完整的PGF：
\[F(z) = \sum\limits_{k=0}^\infty P(T=k)z^k \]显然有\(F(1) = 1\)（概率生成函数的性质：所有概率的和为1），所以：
\[G(1) = \sum\limits_{i\in Border(A)} n^i\cdot 1^{-i}F(1) = \sum\limits_{i\in Border(A)} n^i \]使用哈希或者KMP求一下Border即可（注意自己也是Border，对应了事件\(V\)可能直到把整个\(A\)都加完才发生）。
注：PGF：概率生成函数，OGF：普通生成函数
标签：infty,limits,cdot,sum,生成,歌唱,CTSC2006,Border,王国 From： https://www.cnblogs.com/kyeecccccc/p/16950615.html