神奇的概率生成函数——歌唱王国
Sweetlemon
2020-02-03 23:15:11
### 神奇的概率生成函数——歌唱王国
#### 题意
字符集大小为 $n$。有 $t$ 组数据。
每一组数据包含一个长度为 $m$ 的字符串 $S$。现在有一个空串 $T$，每一次在字符集内随机一个字符加入到 $T$ 的末尾，当 $S$ 是 $T$ 的子串时停止。求停止时 $T$ 的期望长度。
#### 做法简述
思路太清奇了，我也不知道怎么描述这个思路。这篇题解只能做到“尽量讲清楚这个做法”吧。
需要用到：生成函数基本知识（包括求导等）、KMP。
##### 概率生成函数的性质
首先让我们认识一个叫概率生成函数的东西：$f(x)=\sum_{i=0}^{+\infty} \mathrm{P}(X=i)x^i$，也就是 $i$ 次项的系数是随机变量 $X$ 等于 $i$ 的概率。
这个东西有什么用呢？这道题着重用到它的两个性质。
1. $f(1)=1$。$f(1)$ 其实就是把 $f(x)$ 的所有系数加起来，而这里的系数就是概率；因此 $f(1)$ 实际上就是把所有可能情况的概率加起来，于是 $f(1)=1$。
2. 我们要求的是期望，和这个概率生成函数有什么关系呢？想一想，上面的式子想出现期望，是不是需要在 $\mathrm{P}(X=i)$ 上乘一个 $i$ 呀？如何让这个 $i$ 出现呢？求导啊。于是这个式子也就可以理解了：$f'(x)=\sum_{i=1}^{+\infty}i\mathrm{P}(X=i)x^{i-1}$。为了全部加起来，我们令 $x=1$，得到 $f'(1)=\sum_{i=1}^{+\infty}i\mathrm{P}(X=i)=\mathrm{E}(X)$。
总结一下，概率生成函数和它的导函数在 $x=1$ 处的取值都很特殊，分别是 $f(1)=1,f'(1)=\mathrm{E}(X)$。
##### 引入概率生成函数
先设一个变量 $Y$ 表示（任意一次随机的过程中）停止的时候 $T$ 的长度，也就是随机了 $Y$ 个字符的时候恰好随机出 $S$。
引入两个概率生成函数 $f(x)$ 和 $g(x)$，分别表示 $Y=i$ 的概率和 $Y>i$ 的概率。也就是 $f(x)=\sum_{i=0}^{+\infty}\mathrm{P}(Y=i)x^i$，$g(x)=\sum_{i=0}^{+\infty}\mathrm{P}(Y>i)x^i$。
方便起见，我们用 $f_i$ 表示 $f(x)$ 的 $x^i$ 项系数，$g_i$ 同理。那么，$f_i$ 就表示随机了 $i$ 个字符恰好停止的概率，$g_i$ 表示随机了 $i$ 个字符还没有停止的概率。
##### 第一个式子
接下来我们建立一个 $f$ 和 $g$ 的递推式。
$g_{i}=\mathrm{P}(Y>i)=\mathrm{P}(Y\ge i+1)=\mathrm{P}(Y=i+1)+\mathrm{P}(Y>i+1)=f_{i+1}+g_{i+1}$。每一个等号分别是用了定义、整数的离散性、分类讨论（或者说全概率公式）和定义。$i$ 的范围是 $i\ge 0$。
把这个式子整理成生成函数，那么就有 $xg(x)+1=f(x)+g(x)$。$+1$ 是处理边界项 $g_0=1$（因为不可能一个字符也没有就停止了，$Y$ 必定大于 $0$，因此 $g_0=1$）。
由于我们要求的是 $f'(1)$，因此上面的式子整理成 $f(x)=(x-1)g(x)+1$，再求导得 $f'(x)=g(x)+(x-1)g'(x)$，于是有 $f'(1)=g(1)$，这是不是非常好？
##### 第二个式子
接下来的过程就非常奇妙了。
我们设一个新的数列 $h_i\ (i\ge 0)$，表示同时满足以下两个条件（记为事件 $A$）的概率：
1. 随机了 $i$ 个字符还没有出现 $S$
2. 接着**无条件**随机 $m$ 个字符（注意 $m$ 是 $S$ 的长度），且这 $m$ 个字符恰好是 $S$
什么叫“无条件”呢？就是随机这 $m$ 个字符的过程中，有可能还没随机够 $m$ 个，就已经出现 $S$ 了。这种情况下我们强迫它一定要随机够 $m$ 个。
相当于，$h_i$ 表示的是这一个事件 $A$ 的发生概率：
有一天你开始随机，随机了 $i$ 个字符还没有随机出 $S$，你失去了耐心，说：“无论如何，再给我随机 $m$ 个！”然后 $m$ 个过后，你发现这 $m$ 个字符恰好是 $S$！
解释了 $h_i$ 的含义，如何计算 $h_i$ 呢？
**第一种方法**比较简单。上面两个条件是彼此独立的，因此可以把“随机了 $i$ 个字符都没有停止”和“无条件随机 $m$ 个字符，恰好得到 $S$”的概率乘起来，也就是 $h_i=g_i n^{-m}$（注意，$n$ 是字符集大小）。
**第二种方法**比较神奇，运用了分类讨论（或者说全概率公式）。
我们注意到，如果事件 $A$ 发生，那么第一次出现 $S$ 的时刻（也就是上面定义的 $Y$）一定满足 $i<Y\le i+m$（$i+m$ 的时候一定已经出现了 $S$，所以 $Y\le i+m$）。因此我们讨论 $Y$ 的每一个取值。
假设 $Y=y$，那么这个前提的概率就是 $f_y$。下面只需要求出在这个前提下事件 $A$ 发生的概率，再把这个概率乘以 $f_y$ 并全部加起来（根据全概率公式）就好了。
这个前提下事件 $A$ 发生的概率是多少呢？
记 $t=y-i\ (0<t\le m)$。那么 $y$ 时刻（也就是第一次出现 $S$ 的时候），已经随机了这 $m$ 个字符中的 $t$ 个了。如果要发生事件 $A$，就得满足，这 $t$ 个字符恰好是 $S$ 的前 $t$ 个（条件 a），并且后面再随机的 $m-t$ 个字符恰好是 $S$ 的剩余 $m-t$ 个字符（条件 b）。
然而，由于 $y$ 时刻恰好出现了 $S$，那也就意味着这 $t$ 个新的字符也恰好是 $S$ 的那个长度为 $t$ 的后缀。也就是说，这 $t$ 个字符是确定的。条件 a 能够满足，就等价于，这个后缀必须同时也是 $S$ 的前缀——想到了什么？这就是说，这个后缀必须是 $S$ 的 border！（注意，这里和 border 的一些定义有所不同的是，我们认为 $S$ 本身也是 $S$ 的一个 border。也就是说，只要一个串既是 $S$ 的前缀，又是 $S$ 的后缀，那么我们就把这个串叫做 $S$ 的 border。）总结一下，条件 a 等价于这个长度为 $t$ 的后缀是 $S$ 的 border。
条件 b 是概率性的，剩下来的字符和前面的是独立的，因此这 $m-t$ 个字符满足要求的概率就是 $n^{-(m-t)}=n^{t-m}$。
因此，$Y=y,\ t=y-i$ 的**前提下**，同时满足条件 a 和 b 的概率（也就是事件 $A$ 发生的概率）是 $\mathrm{isborder}(t)\times n^{t-m}$，其中 $\mathrm{isborder}(t)$ 的取值为 $1$ 或 $0$，表示长度为 $t$ 的后缀是否是 $S$ 的一个 border。
根据全概率公式，把所有可能情况的概率加起来，事件 $A$ 发生的概率就是 $\sum_{t=1}^{m}f_{i+t}n^{t-m}\mathrm{isborder}(t)$（注意 $t=y-i,\ y=i+t$，因此 $f_y=f_{i+t}$）。
上面的式子换一种写法就是 $h_i=\sum_{S\text{的} t \text{长border}} f_{i+t}n^{t-m}$，这个求和号的意思是对所有 $S$ 的 border 求和，求和的时候把这个 border 的长度带入到被求和式当中的 $t$ 中。
整理一下，我们用两种方法计算 $h_i$，分别得到了 $h_i=g_i n^{-m}$ 和 $h_i=\sum_{S\text{的} t \text{长border}} f_{i+t}n^{t-m}$，因此 $g_i n^{-m}=\sum_{S\text{的} t \text{长border}} f_{i+t}n^{t-m}$。这又是一个关于 $g$ 和 $f$ 的式子！
上面这个式子两边乘以 $n^m$ 得到 $g_i=\sum_{S\text{的} t \text{长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^mg(x)=\sum_{S\text{的} t \text{长border}} x^{m-t}f(x)n^{t}$。
##### 得到答案
上面的式子看上去还是很丑是吧？别忘了我们只要求出 $g(1)$ 就是答案了。
将 $x=1$ 代入上面的式子得到 $g(1)=\sum_{S\text{的} t \text{长border}} f(1)n^{t}$，又根据概率生成函数的性质，$f(1)=1$，因此 $g(1)=\sum_{S\text{的} t \text{长border}} n^{t}$。太神奇了！
根据这个式子，答案就是 $\sum_{S\text{的} t \text{长border}} n^{t}$。因此我们只需要找出 $S$ 的所有 border，把 $n^t$ 累加到答案里就可以了。这个可以用 KMP，或者由于我们可以枚举 border 长度，用哈希判断前后缀是否相等。
时间复杂度 $O(m)$。
特别注意：如果用 KMP 求，一定记得这道题中 $S$ 本身也算 $S$ 的一个 border！
#### 代码实现
式子推完了，代码应该非常容易写。提供我用 KMP 写的代码。
```cpp
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x) \
freopen(x".in","r",stdin); \
freopen(x".out","w",stdout);
#define MAXN 100005
#define MOD 10000
#define N 100000
#define MD(x) (((x)>=MOD)?((x)-=MOD):(0))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读，实现略去
void ayano(io_t x,char spliter='\n'); //快写，本题没用到
int spw[MAXN]; // 字符集大小（题目中的 n）的幂的预处理
int knxt[MAXN]; // KMP 的 next 数组
int arr[MAXN]; // 字符串
int main(void){
int s,testdatas; //s 表示题目中的 n
s=seto()%MOD,testdatas=seto();
spw[0]=1;
for (int i=1;i<=N;i++)
spw[i]=spw[i-1]*s%MOD;
while (testdatas--){
int n=seto(); //表示题目中的 m
// KMP 计算 next
knxt[0]=-1;
for (int i=1;i<=n;i++){
int cur=seto();
arr[i]=cur;
int tnxt=knxt[i-1];
while (tnxt>=0){
if (arr[tnxt+1]==cur)
break;
tnxt=knxt[tnxt];
}
knxt[i]=tnxt+1;
}
int t=n;
int ans=0;
// 在 next 数组上跳，枚举每一个 border
while (t)
ans+=spw[t],MD(ans),t=knxt[t];
//输出答案
putchar(ans/1000+'0'),putchar(ans/100%10+'0'),
putchar(ans/10%10+'0'),putchar(ans%10+'0'),putchar('\n');
}
return 0;
}
```