Luogu

分析

以下统一规定 $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;
}
最后修改：2021 年 03 月 23 日 09 : 58 PM
© 允许规范转载