神奇的概率生成函数——歌唱王国
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;
}
```