洛谷P4548 [CTSC2006]歌唱王国（概率生成函数）

题面

传送门

给定一个长度为\(L\)的序列\(A\)。然后每次掷一个标有\(1\)到\(m\)的公平骰子并将其上的数字加入到初始为空的序列\(B\)的末尾，如果序列B中已经出现了给定序列\(A\)，即\(A\)是\(B\)的子串，则停止，

求序列\(B\)的期望长度。\(L ≤ 10^5\)

题解

好妙啊！

听说原题解是个字符串的复杂做法，然而论文里这个做法简直吊打标算

前置芝士

概率生成函数

我们定义一个形式幂级数\(A(x)\)，称它为离散随机变量\(X\)的概率生成函数，当且仅当对于\(A(x)\)的每一项\(a_i\)，都有\(a_i=P(X=i)\)

容易发现以下几个性质

1.\[A(1)=\sum_{i=0}^\infty P(X=i)=1\]

2.\[A'(x)=\sum_{i=0}^\infty iP(X=i)x^{i-1}=E(X)\]

本题

我们定义一个字符串的前缀\(S[1,i]\)为这个字符串的\(border\)当且仅当\(S[1,i]=S[L-i+1,L]\)，其中\(L\)为串长

定义\(a_i\)，当且仅当\(S[1,i]\)是\(S\)的\(border\)时\(a_i\)为\(1\)，否则\(a_i\)为\(0\)

定义答案的概率生成函数为\(F(x)\)，即\(f_i\)表示掷了\(i\)次骰子游戏结束的概率，以及\(G(x)\)，\(g_i\)表示掷了\(i\)次骰子游戏仍未结束的概率

那么容易发现两个性质

1.\[G(x)+F(x)=1+xG(x)\]

也就是说\(g_i=g_{i+1}+f_{i+1}\)，即如果第\(i\)次未结束，那么第\(i+1\)次只有结束或未结束，\(+1\)是因为常数项

2.\[G(x)\left({1\over m}x\right)^L=\sum_{i=1}^La_iF(x)\left({1\over m}x\right)^{L-i}\]

即如果我们在一个未结束的串后面加上整个\(A\)肯定结束，然而还有可能没有加完整个串就已经结束了。通过分析可知，如果我们加了\(A\)的前\(i\)个字符之后结束，即有\(A[L-i+1,L]=A[1,i]\)，那么根据定义，\(A[1,i]\)是一个\(border\)，然后再把剩下的\(L-i\)个字符加进去就行了

对于\(1\)式，我们对两边求导，再把\(x=1\)代入，得

\[G'(x)+F'(x)=G(x)+xG'(x)\]

\[F'(1)=G(1)\]

即我们所需要求的\(E(x)=F'(1)=G(1)\)

对于\(2\)式，我们把\(1\)代入，在两边同乘上\(m^L\)，得

\[G(1)=\sum_{i=1}^La_im^iF(1)\]

又因为\(F(1)=1\)，最终可以化作

\[E(x)=\sum_{i=1}^La_im^i\]

而对于\(a_i\)我们是可以\(O(L)\)求出来的，直接哈希或者跑\(kmp\)就行了（代码里写的是\(kmp\)）

于是复杂度为\(O(L)\)

//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5,P=1e4;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int bin[N],kmp[N],a[N],n,p,res,pos;
int main(){
//  freopen("testdata.in","r",stdin);
    p=read(),bin[0]=1;fp(i,1,1e5)bin[i]=mul(bin[i-1],p);
    for(int T=read();T;--T){
        n=read();fp(i,1,n)a[i]=read();
        kmp[0]=kmp[1]=0;
        for(R int i=2,j=0;i<=n;++i){
            while(j&&a[j+1]!=a[i])j=kmp[j];
            j+=(a[j+1]==a[i]),kmp[i]=j;
        }
        pos=n,res=0;
        while(pos)res=add(res,bin[pos]),pos=kmp[pos];
        printf("%04d\n",res);
    }
    return 0;
}

洛谷P4548 [CTSC2006]歌唱王国（概率生成函数）

原文：https://www.cnblogs.com/bztMinamoto/p/10560884.html