自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 21:23:40，当前版本为作者最后更新于2020-10-18 23:24:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

欢迎到我的博客查看

Subtask 1

直接枚举 + 后缀全家桶暴力即可。

Subtask 2 & 3

首先我们先简单转化一下题面，变为统计长度为 $n$，字符集大小为 $m$ 的所有字符串，每一个字符串的本质不同子串个数之和，记其为 $S(n,m)$。

善于找规律的同学应该能发现当 $n$ 固定的时候 $S(n,m)$ 是关于 $m$ 的一个 $n$ 次多项式。于是我们可以先用上面的暴力对于每一个 $n$ 求出 $m=1\sim (n+1)$ 时的值，然后插值得出多项式即可。

满分做法

我们发现 $n=20$ 时我们需要求出 $m=1\sim 21$ 时的值，但这个东西是完全没法在考试时限内算出来的（话说有没有少爷机跑出来了啊（雾））。有经验的同学应该能注意到 $n=20$ 暗示了我们这道题的时间复杂度可能是 $O(2^n)$ （？？？），于是我们开始思考。

反向思考，我们考虑每一个长度小于等于 $n$ 且字符集大小为 $m$ 的字符串被多少个长度为 $n$，字符集大小为 $m$ 的字符串包含了。显然枚举这小的子字符串也是要超时的，不过我们考虑到对于一些子字符串，包含它们的指定字符串数量是相同的。更具体的，如果 $w$ 是一个字符串，我们令 $c_w(x)$ 为关于 $x$ 的一个函数，它的第 $i$ 项为系数为 1 当且仅当 $w$ 有一个长度为 $i$ 的周期（我们规定所有字符串都有一个长度为 0 的周期）；否则这一项系数为 0。令 $e_{w,i}$ 为长度为 $i$，字符集为 $m$ 的包含 $w$ 的字符串数量，然后另 $E_w(x)$ 为它关于 $i$ 的普通生成函数。有一个结论：

$$E_w(x)=\frac{x^{|w|}}{(1-mx)(x^{|w|}+(1-mx)c_w(x))} $$

这个的证明可以参看 本次考试 T4 的题解。不过有同学要问了，这道题模数 $1e9+7$ 怎么做求逆？$MTT$ 吗？但由于 $n$ 只有 20，所以我们直接暴力乘法就好了。

然后我们考虑 $O(2^n)$ 枚举所有的 $c_w(x)$，然后算出 $E_w(x)$ 再乘上有多少个字符串 $w$ 的 $c_w(x)$ 为当前枚举的这个东西。我们现在考虑对于一个 $c_w(x)$ 怎么求出有多少个 $w$ 的 $c_w(x)$ 为当前枚举的值。形式化的，对于每一个 $i\in [0,L-1]$，我们知道一个字符串是否有长度为 $i$ 的周期，现在我们要求出满足条件的长度为 $L$ 的字符串个数。我们用二进制数 $v$ 代表这个 $c_w(x)$（因为系数只有 0 和 1），然后记 $f_v$ 为上面那个我们要求的值。

考虑容斥。我们先不考虑 不能有长度为 $x$ 的周期 这个条件，我们只考虑有指定的一些周期的字符串共有多少个，记为 $S_v$。这个可以用并查集简单地做到 $O(n^2)$，也没必要继续优化了（$n$ 才 20 啊喂）。具体地说，如果我们用并查集得到了有这些周期的字符串被分割为了 $K$ 个字符必须相同的下标集合，然后就有 $S_v=m^K$。

然后运用容斥定理，我们对于每一个 $v$，得到它的 $f_v$ 就应该是：

$$f_v=S_v-\sum_{j|i\sub j}f_j$$

然后我们就可以插出多项式从而做出这道题了，不过由于 $n$ 并不是很大所以直接交这个打表程序上去也是可以通过的。时间复杂度 $O(3^n\cdot n^2\log n)$，$\log$ 是多项式求逆的复杂度。

注意到长度为 $n$ 的合法（即 $f_v$ 不为 0）的 $v$ 的数量远小于 $2^n$，下表给出了对于每一个 $n$ 合法的 $v$ 数量（注意这个数量是和 $m$ 无关的，当然 $m=1$ 除外，证明见 Leo J. Guibas and Andrew M. Odlyzko. Periods in strings. J. of Combinatorial Theory series A, 30:19–42, 1981. 的 Section 5 Theorem 5.1），具体详见 OEIS A005434：

n	数量
1
2
3
4
5	6
...
20	116

所以最后时间复杂度应该是 $O(\min\left\{A005434(n)\cdot 2^n,3^n\right\}\cdot n^2\log n)$ 的，实际常数很小。

注：关于上面最开始提到的 $S(n,m)$ 是关于 $m$ 的多项式一点，从上面 $f_v$ 的推导其实可以看出。

代码

运行代码需要用到的 mivik.h