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

[题解] [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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// 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;
}

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

https://mivik.gitee.io/2020/solution/mivik-string-contest-writing/

作者

Mivik

发布于

2020-10-26

更新于

2021-05-31

许可协议

评论