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

求长度为 $n$、字符集大小为 $m$ 的随机字符串的期望本质不同子串个数。

$1\le n\le 20$，$1\le m\le 5\cdot 10^6$

题目链接

---

思路

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))}
$$
这个的证明可以参看我的另一篇题解。不过有同学要问了，这道题模数 $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\subset 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

// Mivik 2020.10.10
#include <mivik.h>

#include <algorithm>
#include <cassert>

MI cin;

const int N = 21;
const int V = 1 << 20;
const int mod = 1000000007;

typedef long long ll;

int n, m, cur_len;
bool ok[V];

inline void upd(int &x) { x += (x >> 31) & mod; }
inline int pro(int x) { return x + ((x >> 31) & mod); }
inline ll fast_pow(ll x, int p = mod - 2) {
	ll ret = 1;
	while (p) {
		if (p & 1) (ret *= x) %= mod;
		(x *= x) %= mod;
		p >>= 1;
	}
	return ret;
}
template<class T> inline void fill_zero(T *first, T *last) { memset(first, 0, sizeof(T) * (last - first)); }

// 找到所有可行的 v 并把他们存到 ok 中
void dfs(int x = 1, int j = 0) {
	static int pre[N], a[N];
	if (x == cur_len + 1) {
		int x = cur_len;
		int ret = 0;
		while (x) {
			ret |= 1 << (cur_len - x);
			x = pre[x];
		}
		ok[ret] = 1;
		return;
	}
	for (int &c = a[x] = 0; c < 2; ++c) {
		int nj = j;
		while (nj && c != a[nj + 1]) nj = pre[nj];
		if (x != 1 && c == a[nj + 1]) ++nj;
		pre[x] = nj;

		dfs(x + 1, nj);
	}
}

// 一种 O(n) 找出一种 v 中自由元个数的算法
// 参考 http://www.lirmm.fr/~rivals/RESEARCH/PERIOD/Web-NFC.pdf
inline int nfc(int v) {
	int l = 0, ret = 0;
	while (true) {
		const int n = cur_len - l;
		int i = 1;
		while (i < n && !((v >> (l + i)) & 1)) ++i;
		if (i == n) return n + ret;
		if (i == 1) return 1 + ret;
		if (i <= (n >> 1))
			l += n - i - n % i;
		else {
			ret += i * 2 - n;
			l += i;
		}
	}
	return ret;
}

struct poly {
	int v[N];
	inline int &operator[](int i) { return v[i]; }
	inline int operator[](int i) const { return v[i]; }
	inline void reset() { memset(v, 0, sizeof(v)); }

	inline void from_binary(int x) {
		for (int i = 0; i < N; ++i) {
			v[i] = x & 1;
			x >>= 1;
		}
	}
	// 计算 a 和 b 的乘积并存储在 this 中
	// 模 (x ^ N)
	inline void from_mul(const poly &a, const poly &b) {
		reset();
		for (int i = 0; i < N; ++i) {
			const int lim = N - i;
			for (int j = 0; j < lim; ++j) upd(v[i + j] += (ll)a[i] * b[j] % mod - mod);
		}
	}
	// 计算 a 的乘法逆元并存储在 this 中
	// 模 (x ^ N)
	inline void from_inv(const poly &a) {
		static poly t, d;
		reset();
		v[0] = fast_pow(a[0]);
		const int lim = N * 2;
		for (int l = 2; l < lim; l <<= 1) {
			t.from_mul(*this, a);
			for (int i = 0; i < N; ++i) t[i] = pro(-t[i]);
			upd(t[0] += 2 - mod);
			d.from_mul(*this, t);
			std::copy(d.v, d.v + std::min(l, N), v);
		}
	}
	// 将此多项式平移 offset 位，等价于乘以 (x ^ offset)
	// 模 (x ^ N)
	inline void shift(int offset) {
		for (int i = N - 1; i >= offset; --i) v[i] = v[i - offset];
		fill_zero(v, v + offset);
	}
};

// 根据 v 算包含此字符串的字符串个数
inline poly containing(const poly &cor) {
	static poly ret, tmp, fin;
	ret = { 1, pro(-m) };
	tmp.from_mul(ret, cor);
	upd(tmp[cur_len] += 1 - mod);
	fin.from_mul(ret, tmp);
	ret.from_inv(fin);
	ret.shift(cur_len);
	return ret;
}

// v 为指定下标的不同字符串有多少
int f[V];

int main() {
	poly p;
	cin > n > m;
	int ans = 0;
	for (cur_len = 1; cur_len <= n; ++cur_len) {
		const int lim = 1 << cur_len;
		fill_zero(ok, ok + lim);
		fill_zero(f, f + lim);
		dfs();
		for (int c = lim - 1; c; --c) {
			if (!ok[c]) continue;
			f[c] = fast_pow(m, nfc(c));
			for (int s = (c + 1) | c; s < lim; s = (s + 1) | c) upd(f[c] -= f[s]);
			p.from_binary(c);
			p = containing(p);
			upd(ans += (ll)f[c] * p[n] % mod - mod);
		}
	}
	cout < (int)((ll)ans * fast_pow(fast_pow(m, n)) % mod) < endl;
}