P4548 [CTSC2006]歌唱王国

题目大意

字符接大小为$c$$T$串初始为空每次等概率往$T$串后加一个字符问$S$串第一次是$T$串的子串的期望长度

题解

设$c$为字符集大小$n$为$S$的长度

设$G(x)={\sum }_{i=0}P(X>i)x^i,F(x)={\sum }_{i=0}P(X=i)x^i$

已知$F(1)=1$而$F^{\prime }(1)$即为所求

$$G(x)+F(x)=\sum _{i=0}P(X\ge i)x^i=xG(x)+1$$

求导

$$G^{\prime }(x)+F^{\prime }(x)=x{G}^{\prime }(x)+G(x)$$

代入$x=1$得

$$F^{\prime }(1)=G(1)$$

所以求出$G(1)$就行了

考虑直接用$G$构造出$F$直接在后面加上一个$S$即$G(x)(\frac{x}{c}{)}^n$但这显然是不对的因为可能中途就已经出现了$S$继续分析中途出现$S$的地方只能是一个$border$

设$A_i=[S_{1,i}=S_{n-i+1,n}]$就可以构造出${\sum }_{i=1}^n{A}_{i}F(x)(\frac{x}{c}{)}^{n-i}$这个式子的含义与$G(x)(\frac{x}{c}{)}^n$是一样的所以${\sum }_{i=1}^n{A}_{i}F(x)(\frac{x}{c}{)}^{n-i}=G(x)(\frac{x}{c}{)}^n$

代入$x=1$

$$G(1)(\frac{1}{c}{)}^n=\sum _{i=1}^n{A}_{i}F(1)(\frac{1}{c}{)}^{n-i}$$

$$G(1)=\sum _{i=1}^n{A}_i{c}^i$$

$\text{code}$

#include<cstdio>
using namespace std;
const int N=1e5+100;
int c,T,n,s[N+10],kmp[N+10],a[N+10],Ans[5],Pow[N+10];
int main()
{
	scanf("%d %d",&c,&T);
	Pow[0]=1;for(int i=1;i<=N;i++) Pow[i]=Pow[i-1]*c%10000;
	for(;T--;)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%s",&s[i]);
		int j=0;
		for(int i=2;i<=n;i++)
		{
			while(j&&s[j+1]!=s[i])
				j=kmp[j];
			if(s[j+1]==s[i]) j++;
			kmp[i]=j;
		}
		int ans=0;
		j=n;
		while(j!=0) ans+=Pow[j],j=kmp[j];
		for(int i=1;i<=4;i++) Ans[i]=ans%10,ans/=10;
		for(int i=4;i>=1;i--) printf("%d",Ans[i]);
		puts("");
	}
	return 0;
}