Link
Description
字符集大小 \(c\)。\(Q\) 次询问，每次给定长为 \(m\) 的串 \(S\)。每秒可随机生成字符集的一个字符，问期望多少秒后得到串 \(S\)。
Solution
令 \(f_n\) 表示第 \(n\) 秒成功的概率，\(g_n\) 表示第 \(n\) 秒失败的概率，也即在第 \(n\) 秒之后成功的概率。这个定义蕴含了前 \(n-1\) 秒都失败。令
\[F(x)=\sum_{n\geq 0} f_n x^n,G(x)=\sum_{n\geq 0} g_n x^n \]显然有 \(F(1)=\sum_{n \geq 0} f_n=1\)
那我们要求的实际上就是
\[F'(1)=\sum_{n\geq 1} nf_n 1^{n-1}=\sum_{n\geq 0} nf_n \]首先可以得到一个很显然的式子
\[f_n+g_n=[n\geq 1]g_{n-1}+[n=0] \]左边表示第 \(n\) 秒成功的概率加上第 \(n\) 秒不成功的概率，实际上就是在 \(n-1\) 秒之后成功的总概率。特别的，当 \(n=0\)，\(f_0+g_0=0+1=1\)。那么就得到
\[F(x)+G(x)=xG(x)+1 \]对恒等式两边关于 \(x\) 求导，得到
\[F'(x)+G'(x)=xG'(x)+G(x) \]带入 \(x=1\)
\[F'(1)+G'(1)=1G'(1)+G(1) \] \[F'(1)=G(1) \]所以只需要求出 \(G(1)\)。
根据定义，我们还可以列出一个式子
\[g_n(\frac{1}{c})^m=\sum_{i=1}^m a_if_{n+i} (\frac{1}{c})^{m-i} \]左边表示在 \(n\) 秒失败后，强行在后面填一个 \(S\)，使得其成功。但事实上，有时候不需要添加 \(S\) 个字符，因为前面可能已经有了一段现成的。如图。
我们可能在位置 \(n+i\) 就成功了，也就是说红色部分加上 \(i\) 和 \(S\) 是相同的，那自然就得出 \(i\) 那一段是 \(S\) 的一个 border。我们用 \(a_i\) 表示 \(S(1,i)\) 是不是 \(S\) 的一个 border。而 \(f_{n+i}\) 就蕴含了 \(n+i\) 的最后 \(m\) 个组成 \(S\)，我们又多余地加了一段，所以再乘上 \((\frac{1}{c})^{m-i}\)，那么就得到了右式。
化简得
\[g_n=\sum_{i=1}^m a_i f_{n+i} c^i \]也即
\[G(x)=\sum_{i=1}^m a_i \frac{F(x)}{x^i} c^i \]那么
\[F'(1)=G(1)=\sum_{i=1}^m a_i F(1) c^i=\sum_{i=1}^m a_i c^i \]所以只需要 kmp 处理出 border 就可以了，复杂度 \(O(Qm)\)
#include<stdio.h>
const int Mod=1e4;
const int N=1e5+7;
inline int read(){
int x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag? x:-x;
}
int n,T,kmp[N],a[N],f[N];
int main(){
n=read()%Mod; T=read();
while(T--){
int m=read();
for(int i=0;i<m;i++)
f[i]=0,a[i]=read();
for(int i=1,j=0;i<m;i++){
while(j&&a[i]!=a[j]) j=kmp[j];
if(a[i]==a[j]) kmp[i+1]=++j;
else kmp[i+1]=0;
}
for(int i=m;i;i=kmp[i]) f[i]=1;
int ans=0;
for(int i=1,ret=n;i<=m;i++,ret=ret*n%Mod)
ans=(ans+f[i]*ret)%Mod;
printf("%04d\n",ans);
}
}