分析
以下统一规定 $n$ 为字符集大小，$m$ 为名字长度。
设 $f_i$ 表示长度为 $i$ 时结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。
设 $f_i$ 的概率生成函数为 $F(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。
根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。
分析一下可以列出这样一个式子
$$
xG(x)+1=F(x)+G(x) \tag{1} \label{1}
$$
这个式子的意义是加一个字符后可能结束也可能没有结束。感觉是废话，但是真的可以列一个式子
再分析一下可以列出这样一个式子
$$
G(x)\cdot\left(\frac{1}{n}x\right)^m=\sum_{i=1}^ma_i\cdot F(x)\cdot\left(\frac{1}{n}x\right)^{m-i} \tag{2} \label{2}
$$
这里的 $a_i$ 表示 $[1,i]$ 是否是名字的一个 border 。
这个式子的意义是在一个未结束的序列后加上名字一定会结束，但是有可能在没有到 $m$ 个字符时就结束了，此时添加的序列是名字的一个 border 。
把 $\eqref{1}$ 求导可以得到
$$
\begin{align}
xG'(x)+G(x)&=F'(x)+G'(x)\\
F'(x)&=(x-1)G'(x)+G(x) \tag{3} \label{3}
\end{align}
$$
把 $x=1$ 代入 $\eqref{3}$ 可以得到
$$
F'(1)=G(1) \tag{4} \label{4}
$$
把 $x=1$ 代入 $\eqref{2}$ 可以得到
$$
\begin{align}
G(1)\cdot\left(\frac{1}{n}\right)^m&=\sum_{i=1}^ma_i\cdot F(1)\cdot\left(\frac{1}{n}\right)^{m-i}\\
G(1)&=\sum_{i=1}^ma_i\cdot F(1)\cdot n^i\\
G(1)&=\sum_{i=1}^ma_i\cdot n^i \tag{5} \label{5}
\end{align}
$$
联立 $\eqref{4}\eqref{5}$ 可以得到
$$
F'(1)=\sum_{i=1}^ma_i\cdot n^i
$$
用 KMP / hash 求出 $a_i$ 即可。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
const int mod=10000;
int n,t,m;
int s[N],pw[N],nxt[N];
inline void solve() {
m=read();
for (re int i=pw[0]=1;i<=m;++i) pw[i]=pw[i-1]*n%mod;
for (re int i=1;i<=m;++i) s[i]=read();
for (re int i=2,j=0;i<=m;++i) {
while (j&&s[j+1]!=s[i]) j=nxt[j];
if (s[j+1]==s[i]) ++j;
nxt[i]=j;
}
int ans=0;
for (re int i=m;i;i=nxt[i]) ans=(ans+pw[i])%mod;
printf("%04d\n",ans);
}
int main() {
n=read(),t=read();
for (re int i=1;i<=t;++i) solve();
return 0;
}
8 条评论
你的$G(x)$不应该是普通型生成函数吗？
你可以这么理解吧...只是把它叫做概率生成函数而已 ...
应该是 f_i 的普通生成函数，长度为 i 时结束的概率生成函数吧（瞎说的
改了qaq
我是错的，您原来那份是对的。麻烦您改回来吧...抱歉！
等下好像两种说法都有，那我还是坚持下我原来的观点吧orz。
羡慕能听 laofu 讲课的 ...
QAQ