概率生成函数
认识概率生成函数，形如
\[f(x) = \sum_{i = 0}^{+\infty}P(X = i)x^i \]也就是 i 次项的系数是随机变量 X 等于 i 的概率。
这个东西有两个用处：
1 关于概率
\(f(1) = 1\) 其实就是把 \(f(x)\) 的所有系数加起来，而这里的系数就是概率
2 关于期望
想一想，上面的式子想出现期望，是不是需要在 \(P(X=i)\) 上乘一个 i 呀？如何让这个 i 出现呢？求导啊！
\[f'(x) = \sum_{i = 0}^{+\infty}iP(X = i)x^{i - 1} ~~~\Rightarrow~~~f'(1) = \sum_{i = 0}^{+\infty}iP(X = i) \]综上所述
\[f(1) = 1~~~~f'(1)=E(X) \]先设一个变量 \(Y\) 表示（任意一次随机的过程中）停止的时候 \(T\) 的长度，也就是随机了 \(Y\) 个字符的时候恰好随机出 \(S\)。
引入两个概率生成函数 \(f(x)\) 和 \(g(x)\) ，分别表示 \(Y=i\) 的概率和 \(Y>i\) 的概率。也就是
\[f(x) = \sum_{i = 0}^{+\infty}P(Y = i)~~~~~g(x) = \sum_{i = 0}^{+\infty}P(Y > i) \]\(f_i\) 表示 \(f(x)\) 的 \(x^i\) 次方系数，也就是 \(Y = i\) 的概率， \(g_i\) 同理。
接下来就可以建立一些递推式子：
\[g_i = f_{i + 1}+g_{i + 1} (i \geq 1) \]生成函数中则为（ \(+1\) 是因为处理边界情况）：
\[xg(x) + 1 = f(x) + g(x) ~~~\Rightarrow~~~f(x) = (x-1)g(x) + 1 \]再求导(函数乘积求导公式\([g(x)f(x)]' = g(x)'f(x) + f(x)'g(x)\))：
\[f'(x) = (x - 1)g'(x) + g(x) \]过程2
我们设一个新的数列 \(h_i(i \geq 0)\) 表示同时满足下列两个条件 （记为事件A） 的概率：
1.随机了 \(i\) 个字符但没出现 \(S\)
2.接着无条件随机 \(m\) 个字符( \(m\) 是 \(S\) 长度) ，且 \(m\) 个字符刚好为 \(S\)
什么叫“无条件”呢？就是随机这 \(m\) 个字符的过程中，有可能还没随机够 \(m\) 个，就已经出现 \(S\) 了。这种情况下我们强迫它一定要随机够 \(m\) 个。
相当于，\(h_i\) 表示的是这一个事件 \(A\) 的发生概率：
如何计算 \(h_i\)？
第一种方法
两事件相互独立，概率乘起来，即有：
\(h_i = g_in^{-m}\)
第二种方法
如果事件 \(A\) 发生，则一定满足 \(i< Y \leq i + m\) ，我们讨论 \(Y\) 每一个取值
假设\(Y = y\) ，这个前提的概率是 \(f_i\) ，我们求出在这个前提下事件 \(A\) 发生的概率乘起来并且将\(Y = y ~~~~~~ y \in (i,i+m]\) 的所有概率加起来就是事件 \(A\) 发生的概率 \(h_i\)
设 \(t = y - i\) 也就是代表无条件随机 \(t\) 个字符就出现 \(S\)
重点
那么字符串 \(S_0 - S_t\) 一定为一个前缀(因为从 \(0-t\) )
那么字符串 \(S_0 - S_t\) 一定为一个后缀(因为我们从 \(t\) 结束的 )
也就是 \(S\) 的 \(border\)
概率也就好求了
条件 \(b\) 是概率性的，剩下来的字符和前面的是独立的，因此这 \(m−t\) 个字符满足要求的概率就是 \(n^{−(m−t)}=n^{t−m}\)。
因此在 \(Y = y,t=y-i\) 条件下，事件 \(A\) 的概率是 \([S_0 - S_t是一个border]n^{t-m}\)
根据全概率公式，把所有可能情况的概率加起来，事件 A 发生的概率 \(h_i\) 就是
\[\sum_{t=1} ^ {m}f_yn^{t - m}[S_0 - S_t是一个border] , t = y - i~~\Rightarrow~~ h_i = \sum_{t=S的border长} f_{i+t}n^{t - m} \]综上，根据两种方法求出的 \(h_i\) 联立
\[g_in^{-m} = \sum_{t=S的border长} f_{i+t}n^{t - m}\\ \Rightarrow g_i = \sum_{t=S的border长} f_{i+t}n^{t} \]把 \(g(x)\) 乘以 \(x^m\)，第 \(i+m\) 项的系数变成了 \(g^i\)。
把 \(f(x)\) 乘以 \(x^{m−t}\)，第 \(i+m\) 项的系数变成了 \(f_{(i+m)−(m−t)}=f_{i+t}\)
所以
\[x^{m} * g(x) = \sum_{t=S的border长} x^{m - t}f(x)n^{t} \]我们要求期望，也就是 \(g(1)\)
\[g(1) = \sum_{t=S的border长} f(1)n^{t} \]翻到前面可以看到 \(f(1)\) 是总概率是 \(1\)
得到：
\[g(1) = \sum_{t=S的border长} n^{t} \]\(border\) 用 kmp 求一下就可以啦（本题 \(S\) 本身也是 \(S\) 的border）
标签：infty,概率,函数,sum,生成,随机,border,个字符 From： https://www.cnblogs.com/hfjh/p/17446556.html