[题解] [Mivik 的字符串公开赛] Mivik 的标题

给定 $n$、$m$ 和字符串 $S$，问长度为 $n$、字符集大小为 $m$ 的随机字符串中包含 $S$ 作为子串的概率。答案对 $998244353$ 取模。

$1\le |S|\le n\le 10^5$，$1\le m\le 10^8$

题目链接

---

思路

Subtask 1

输出 1 即可。

Subtask 2

对笔名跑 KMP，建立矩阵然后快速幂即可。

满分做法

为了方便描述，我们定义 $\alpha$ 类字符串为整个字符串中只出现一次名字且出现位置为字符串末尾的字符串。例如名字是 mivik，那么 iammivik 是 $\alpha$ 类字符串，而 mivikmivik 不是。

定义 $f_i$ 为长度为 $i$ ，字符集大小为 $m$ 的字符串中 $\alpha$ 类字符串的个数。然后定义 $F(x)$ 为 $f$ 的普通生成函数。同时定义 $g_i$ 为长度为 $i$，字符集大小为 $m$ 的字符串中完全没有出现名字的的字符串个数，并令 $G(x)$ 为它的普通生成函数。

于是我们得到一个显然的式子：
$$
G(x)\cdot mx+1=F(x)+G(x)
$$
这个式子的含义是，我们在一个还没有出现过名字的字符串后面加上一个字符（有 $m$ 种），新的字符串可能包含名字也可能不包含，于是就得到：
$$
G(x)=\frac{1-F(x)}{1-mx}\tag1
$$
然后我们定义一个关于名字（用 $S$ 表示）的多项式 $c(x)$：
$$
c(x)=\sum_{i=0}^{L-1}[\text{i is a period of S}]\cdot x^i
$$
也就是说，这个多项式的第 $i$ 项系数为 1，当且仅当名字有一个长度为 $i$ 的周期；否则这一项系数为 0。注意我们定义一个字符串总有一个长度为 0 的周期。举例来说，假如名字是 abab，由于这个字符串分别有长度为 0、2 的周期，那么 $c(x)=1+x^2$。

现在我们考虑在一个还没出现过名字的字符串后面加上名字，那么这个新的字符串必定包含了名字（废话）。不过这个新的字符串不一定是在末尾包含了名字，可能是刚加上一个 border 就已经包含了。形式化的，我们把这个新的字符串写成 ABC 的形式，其中 A 是原来还没出现过名字的字符串，BC 拼起来是名字，然后 AB 是一个 $\alpha$ 类字符串。举个例子，假设名字是 abcab，那么有一个没出现过名字的字符串 aaaabc，然后我们在它后面接上笔名就变成了 aaaabcabcab，此时 A 为 aaaabc、B 为 ab、C 为 cab，因为 AB 是 aaaabcab，末尾恰好第一次出现了名字。

我们注意到，要满足这种拆分，那么 C 的长度必定为名字的一个周期的长度，并且 C 是名字的后缀。于是我们考虑到对于每一个 AB（也就是 $\alpha$ 类字符串），我们把它的末尾添加上一个长度为周期长度的名字的后缀——这样我们就会得到上文提到的所有“新的字符串”。于是我们得到了下面的等式：
$$
G(x)\cdot x^L=F(x)\cdot c(x)
$$
我们把 $(1)$ 式代入进去，展开得到：

$$ \begin{aligned} \frac{1-F(x)}{1-mx}\cdot x^L&=F(x)\cdot c(x)\\ \frac{x^L+(1-mx)\cdot c(x)}{1-mx}F(x)&=\frac{x^L}{1-mx}\\ F(x)&=\frac{x^L}{x^L+(1-mx)\cdot c(x)} \end{aligned} $$

于是我们就可以算出 $F(x)$ 了。考虑怎么求出答案，即包含了名字的字符串总数。我们考虑到每一个包含了这个名字字符串的字符串都必定有一个第一次出现名字的位置，也就是说一个包含名字的字符串能唯一对应到一个 $\alpha$ 类字符串。于是我们只需要对每一个 $\alpha$ 类字符串在后面任意加字符即可。假设长度为 $n$，字符集为 $m$ 的字符串中包含了名字的字符串数目是 $e_i$，其生成函数为 $E(x)$，那么我们有：

$$ \begin{aligned} E(x)&=\sum_{i=0}F(x)\cdot (mx)^i\\ E(x)&=\frac{x^L}{(1-mx)\left(x^L+(1-mx)\cdot c(x)\right)} \end{aligned} $$

然后直接多项式求逆展开就好了。

题外话，上文提到的 $c(x)$ 实际使用很多，不过国内几乎没有什么资料，有个名字是字符串的 Autocorrelation Function（自相关函数），可以到 维基百科 看看。

代码

mivik.h

代码