[CTSC2006]歌唱王国

Tags：题解

题意

链接：在空串后不断随机添加字符，直到出现串$S_i$为止。求最终串的期望长度。$\sum |S_i|\le 5*10^6$

题解

以下内容来自$YMD$的2018年集训队论文

很奇怪的生成函数题：

令$f[i]$表示串最终长度为$i$的概率，$g[i]$表示到达长度$i$还没有结束的概率。分别对应生成函数$F(x),G(x)$。最后要求的就是$F'(1)$（求导，相当于每个概率都乘上了指数也就是长度，变成了期望）。

会有两个式子：$$G(x)x+1=F(x)+G(x)$$$$G(x)(\frac{1}{m}x)^L=\sum_{i=1}{L}a_iF(x)(\frac{1}{m}x)^{L-i}$$第一个式子：在没有结束的串后随意添加一个字符，可能结束也可能没有结束，+1是为了补齐余项。

第二个式子：$L$表示$|S|$，$m$是字符集，$(bool)a_i$表示$i$是不是一个$border$。在没有结束的串后加$S$，可能加到第$L-i$个字符就结束了，这个时候要求$i$是原串的$border$。

这里$border$的含义是$S_{1...i}=S_{n-i+1...n}$。

将第一个式子求导：$$F'(x)+G'(x)=G'(x)*x+G(x)$$故$F'(1)=G(1)$

将$x=1$代入第二个式子得$$G(1)(\frac{1}{m})^L=\sum_{i=1}La_iF(1)(\frac{1}{m})^{{L-i}$$又因为$F(1)=1$（概率和为1），所以$$F'(1)=G(1)=\sum_{i=1}}{L}a_im^i$$用KMP求每个位置上的$Border$就好了

代码

#include<iostream>

using namespace std;

const int N=1e5+10,mod=1e4;

int s[N],v[N],nxt[N],l,n,t;

int main()

{

    cin>>n>>t;v[0]=1;

    for(int o=1;o<=t;o++)

    {

        int l,ans=0;cin>>l;

        for(int i=1;i<=l;i++) scanf("%d",&s[i]),v[i]=v[i-1]*n%mod;

        for(int i=2;i<=l;i++)

        {

            int j=nxt[i-1];

            while(s[i]!=s[j+1]&&j) j=nxt[j];

            nxt[i]=s[i]==s[j+1]?j+1:j;

        }

        for(int p=l;p;p=nxt[p]) (ans+=v[p])%=mod;

        cout<<ans/1000%10<<ans/100%10<<ans/10%10<<ans%10<<endl;

    }

}

巴特西

[CTSC2006]歌唱王国

[CTSC2006]歌唱王国

题意

题解

代码

最新文章

热门文章