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

· · 题解

欢迎到我的博客查看

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 1
2 2
3 3
4 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