[CTSC2006]歌唱王国 [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;
    }
}