给定一个由且仅由字符$'H','T'$构成的字符串$S$

给定一个最初为空的字符串$T$,每次随机地在$T$的末尾添加$'H'$或者$'T'$

问当$S$为$T$的后缀时,在末尾添加字符的期望次数

 

妙啊！

设$f_i(0\leq i \leq n-1)$表示（在$T$的末尾匹配$S_{1\cdots i}$）到（在$T$的末尾匹配$S_{1\cdots i+1}$）期望添加多少个字符

①有$\frac12$的概率直接匹配，需要添加$1$个字符

②另外$\frac12$的概率失配，需要添加更多字符

⑨

我们来看看②，为了解决问题，我们引入$go_{i,j}(0\leq i\leq n-1,j\in\{'H','T'\})$表示当已经在$T$的末尾匹配$S_{1\cdots i}$时在$T$的末尾添加字符$j$能匹配到的最远位置

首先假设我们计算好了$go_{1\cdots i-1,'H'\cdots'T'}$，想计算$go_{i,'H'\cdots'T'}$

若$S_{i+1}='H'$，则$go_{i,'H'}=i+1$，$go_{i,'T'}=go_{next_i,'T'}$

若$S_{i+1}='T'$，则$go_{i,'H'}=go_{next_i,'H'}$，$go_{i,'T'}=i+1$

其中$next_i$代表最大的$k\lt i$使得$S_{1\cdots k}=S_{i-k+1\cdots i}$，与kmp中的$next$含义相同

有了$go_{i,j}$，我们现在可以解决②了

失配之后用$go_{i,j}$找到再次匹配的位置，然后一路添加字符直到到达$S_{i+1}$

若$S_{i+1}='H'$，则$f_i=\frac12+\frac12(1+\sum\limits_{go_{i,'T'}\leq j\leq i}f_j)$

整理得$f_i=2+\sum\limits_{go_{i,'T'}\leq j\leq i-1}f_j$

若$S_{i+1}='T'$，则$f_i=\frac12+\frac12(1+\sum\limits_{go_{i,'H'}\leq j\leq i}f_j)$

整理得$f_i=2+\sum\limits_{go_{i,'H'}\leq j\leq i-1}f_j$

综上，我们先用kmp预处理出$next_i$，然后用$next_i$预处理出$go_{i,j}$，最后用$go_{i,j}$算出$f_i$

递推中的$\sum$边算边累加即可，最后的答案为$f_0+f_1+\cdots+f_{n-1}$

#include
     
      #include
      
       #define mod 1000000007char s[1000010];int pi[1000010],f[1000010],sumf[1000010],go[1000010][2],n,i,j;int main(){	scanf("%s",s+1);	n=strlen(s+1);	pi[1]=0;	j=0;	for(i=2;i<=n;i++){		while(j&&s[i]!=s[j+1])j=pi[j];		if(s[i]==s[j+1])j++;		pi[i]=j;	}	//0:H 1:T	for(i=0;i