「CTSC 2006」歌唱王国

Problem

Description

给定一个长度为 L 的序列 A ,每次掷一个标有 1\sim m 数字的公平骰子并将得到的数字加入序列 B 的末尾,当序列 B 中已经出现了序列 A (即 A B 的子串)时停止。
求期望的掷骰子次数。

Constraints

1\le T\le 50,1\le m,L\le 10^{5}

Solution

Analysis

f_{i} 为掷 i 次骰子时恰好结束的概率, g_{i} 为掷 i 次骰子时尚未结束的概率, F(x) \left\{f_{i}\right\} 的 OGF, G(x) \left\{g_{i}\right\} 的 OGF。

b_{i}=\left[A\left[1,i\right]=A\left[L-i+1,L\right]\right] ,有:

F(x)+G(x)=1+x\cdot G(x)

两边求导得:

\begin{aligned} F'(x)+G'(x)&=G(x)+x\cdot G'(x)\\ F'(1)&=G(1) \end{aligned}

又有:

\begin{aligned} \left(\frac{x}{m}\right)^{L}G(x)&=\sum_{i=1}^{L}b_{i}\left(\frac{x}{m}\right)^{L-i}F(x)\\ G(x)&=\sum_{i=1}^{L}b_{i}m^{i}x^{-i}F(x)\\ G(1)&=\sum_{i=1}^{L}b_{i}m^{i} \end{aligned}

则答案为

\sum_{i=0}^{+\infty}f_{i}i=F'(1)=G(1)=\sum_{i=1}^{L}b_{i}m^{i}

\left\{b_{n}\right\} 本质即为 A 的 border 集合,用 KMP 即可快速求出。

时间复杂度 O\left(Tn\right)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>

using i64=long long;
using uchar=unsigned char;

constexpr int maxn(100000);

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

struct IOManager{
inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}
};
}IOManager::IOManager io;

inline void calcnxt(const int*const&s,const int&len,int*const&nxt){
for(int i=2,j=0;i<=len;nxt[i]=(j+=(s[i]==s[j+1])),++i)
for(;j&&s[i]!=s[j+1];j=nxt[j]);
}

int s[maxn+1],
nxt[maxn+1],
pwn[maxn+1];
uchar is[maxn+1];

int main(){
const int n=io;
int v=pwn[0]=1,las=1;
for(int T=io;T;--T){
const int l=io;
for(int i=1;i<=l;++i)
s[i]=io;
calcnxt(s,l,nxt);

for(;las<=l;++las)
pwn[las]=(v=v*n%10000);

for(int i=l;i;i=nxt[i])
is[i]=1;

int ans=0;
for(int i=1;i<=l;++i)
if(is[i])
ans+=pwn[i];
printf("%04d\n",ans%10000);

for(int i=l;i;i=nxt[i])
is[i]=0;
}

return 0;
}