算法疑难杂症

Golomb自描述序列

字数统计: 2.3k字   |   阅读时长: 11分

摘要: 前缀和高级技巧

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们来看一个网友投稿的问题：Golomb 自描述序列。这个问题涉及到的算法点非常基础，就是前缀和。但是思维量非常大，思路很难梳理清楚。

Golomb 序列在 OEIS 中有收录，其中有关于该序列的更多信息，可以参考 https://oeis.org/A001462 。本文主要解决 $n = 2e15$ 级别的输入下，$G(n)$ 的计算问题。

Golomb 序列

在数学中，Golomb 序列 $G(n)$ 是一个非递减整数序列，从 $G(1) = 1$ 开始，$G(n)$ 表示序列中 $n$ 出现的次数。前几个值如下：

1
2
n:    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
G(n): 1, 2, 2, 3, 3, 4, 4, 4, 5, 5,  5,  6,  6,  6,  6,  7,  ...

对给定的正整数 $n$，算出 $G(n)$ 的值。

提示：

1
2
3
对于30%的数据，1 <= n <= 1e6
对于70%的数据，1 <= n <= 1e9
对于100%的数据，1 <= n <= 2e15

暴力法

首先初始时 $G(1) = 1, G(2) = 2$，考虑如何枚举 $3 \leq i \leq n$ 依次求出 $G(i)$，最终求出 $G(n)$。维护两个指针，$i, j$，初始时均为 2。

对于每个 $i$，在 $G$ 的末尾写 $G(i)$ 个 $i$，然后将 $j$ 推到 $j + G(i)$，然后继续推导 $i + 1$。

过程中 $j$ 会比 $i$ 先达到 $n$，当 $j > n$ 时返回。这样就可以在 $O(n)$ 内预处理出 $[1, n]$ 范围内的 $G(n)$。之后即可以 $O(1)$ 应对 $[1, n]$ 范围内的查询了。

代码 (Python)

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
class Golomb:
    def __init__(self, MAXN):
        self.MAXN = MAXN
        self.bruteforce(MAXN)

    def bruteforce(self, n):
        self.G = [0] * (n + 1)
        self.G[1] = 1
        self.G[2] = 2
        i = j = 2
        while i <= n and j <= n:
            for _ in range(self.G[i]):
                self.G[j] = i
                j += 1
                if j > n:
                    break
            i += 1

    def query(self, n):
        return self.G[n]


if __name__ == "__main__":
    MAXN = int(2e6)
    golomb = Golomb(MAXN)

    for i in range(1, 30):
        print("{}: {}".format(i, golomb.query(i)))

    for i in range(int(1e6), int(1e6) + 30):
        print("{}: {}".format(i, golomb.query(i)))

优化1

序列 $G$ 是按照 $G(1)$ 个 $1$，$G(2)$ 个 $2$，$G(3)$ 个 $3$，$G(4)$ 个 $4$ 这样若干个部分依次排列的。

要求出 $G(n)$，我们可以看 $n$ 这个下标落在序列的哪一部分里，比如说 $n$ 落在 $G(k)$ 个 $k$ 的这一段里，那么 $G(n)$ 就等于 $k$。

记 $G(i)$ 的前缀和为 $S(i) = \sum\limits_{j=1}\limits^{i}G(j)$，于是对于 $S(k) < n \leq S(k+1)$ 的范围，有 $G(n) = k+1$，这就是我们前面说的：$n$ 落在了 $G(k+1)$ 个 $k+1$ 这一段里。

因此可以依次枚举 $i = 1, 2, \cdots$，记录前缀和 $S$，直至枚举到 $i$ 时有 $S(i-1) < n \leq S(i)$，即得 $G(n) = i$。

当我们以 $O(n)$ 预处理 $[1, n]$ 范围内的 $G(n)$ 时，可以同时预处理出 $S(n)$。这样可以通过二分在 $O(\log n)$ 时间复杂度响应 $O(S(n))$ 级别的输入。

代码 (Python)

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
import bisect

class Golomb:
    def __init__(self, MAXN):
        self.MAXN = MAXN
        self.optim1(MAXN)

    def query(self, n):
        return bisect.bisect_left(self.S, n)

    def optim1(self, n):
        self.G = [0] * (n + 1)
        self.G[1] = 1
        self.G[2] = 2
        self.S = [0] * (n + 1)
        self.S[1] = 1
        i = j = 2
        while i <= n and j <= n:
            for _ in range(self.G[i]):
                self.G[j] = i
                self.S[j] = self.S[j - 1] + self.G[j]
                j += 1
                if j > n:
                    break
            i += 1


if __name__ == "__main__":
    MAXN = int(1e6)
    golomb = Golomb(MAXN)

    for i in range(1, 30):
        print("{}: {}".format(i, golomb.query(i)))

    for i in range(int(1e6), int(1e6) + 30):
        print("{}: {}".format(i, golomb.query(i)))

    for i in range(int(1e9), int(1e9)+30):
        print("{}: {}".format(i, golomb.query(i)))

可以看到为了计算 $G(1e9)$，暴力法的预处理过程需要枚举到 $1e9$，然后才能在 $O(1)$ 下响应 $n = 1e9$ 级别的查询。

而通过序列 $G$ 的性质，引入前缀和后，可以在仅预处理到 $1e6$ 的情况下，即可在 $O(\log (1e6))$ 下响应 $n = 1e9$ 级别的查询。

优化2

优化1 是将序列 $G(n)$ 按照不同的连续数字分为若干个组，也就是按照 $G(1)$ 个 $1$，$G(2)$ 个 $2$，$G(3)$ 个 $3$，$G(4)$ 个 $4$ 这样若干个部分依次排列的。

序列 $G(n)$ 还可以按照不同的重复次数分为若干个组，也就是重复 $k$ 次的视为为一组。例如当 $k = 2$ 时，重复 2 次的组为 2, 2, 3, 3，当 $k = 3$ 时，重复 3 次的组为 4, 4, 4, 5, 5, 5，以此类推。

可以发现，重复 $k$ 次的组的元素个数为 $k G(k)$，其含义是：序列中 $k$ 的出现次数为 $G(k)$，也就是有 $G(k)$ 个不同的 $x$ 使得 $G(x) = k$，每一个 $x$ 都重复了 $k$ 次，因此重复 $k$ 次的组的元素个数为 $kG(k)$。

记 $T(k) = \sum\limits_{i=1}\limits^{k}iG(i)$，当 $n$ 很大时，为了确定 $G(n)$，可以首先找到 $k$ 使得：

这说明 $G(n)$ 在重复次数为 $k+1$ 的组中，组的元素个数为 $(k+1)G(k+1)$，有 $G(k+1)$ 个数字重复了 $k+1$ 次。

记 $G(n)$ 的前缀和为 $S(n) = \sum\limits_{i=1}\limits^{n}G(i)$，于是对于 $S(k) < x \leq S(k+1)$ 的范围，有 $G(x) = k+1$。也就是下面这 $G(k+1)$ 个数是重复了 $k+1$ 次的;

1
S(k) + 1, S(k) + 2, ..., S(k) + G(k+1)

下面要解决的问题就是：上面这 $G(k+1)$ 个重复了 $k+1$ 次的数字中，$G(n)$ 到底是其中的哪一个。

例如考虑 $n=6$ 的情况，可以求出 $k=2$ 时，有：

也就是说 $G(6)$ 在重复次数为 $3$ 的组中，这个组的元素个数为 $3G(3) = 6$，也就是有 $G(3) = 2$ 个数字重复了 $3$ 次。进一步，$3 = S(2) < x \leq S(3) = 5$ 范围内有 $G(x) = 3$，因此 $G(6)$ 的范围是 $4, 5$。$G(6)$ 到底是这两个数字中的哪一个是下一步要解决的问题。

$T(k)$ 表示重复次数小于等于 $k$ 的元素个数，$n - T(k)$ 就是重复次数为 $k + 1$ 的数贡献的。

  • 如果 $n - T(k) \leq k + 1$，那么 $n$ 就在 $k+1$ 个 $S(k) + 1$ 这一小段中，于是 $G(n) = S(k) + 1$；
  • 如果 $k + 1 < n - T(k) \leq 2(k + 1)$，那么 $n$ 就在 $k+1$ 个 $S(k) + 2$ 这一小段中，于是 $G(n) = S(k) + 2$；

以此类推，可以发现：

通过以上推导过程可以知道，当 $n$ 很大时为了计算 $G(n)$，我们只需要知道 $G(1), \cdots, G(k+1)$ 即可（顺便也就知道了 $S(1),\cdots,S(k)$、$T(1),\cdots,T(k)$），其中 $k$ 就是满足 $T(k) < n \leq T(k+1)$。而 $k$ 是比较小的，因此可以预处理比较短的数组（$G, S, T$）即可高效响应较大的查询。

从小到大预处理 $G(i)$，同时预处理 $S(i)$ 和 $T(i)$，直至 $T(i)$ 大于 $n$ 的最大值，也就是 $T(i) > 2e9$ 时停下。

以 $O(k)$ 预处理出 $G(k)$、$S(k)$、$T(k)$ 之后，就可以 $O(\log k)$ 响应 $O(T(k))$ 级别的查询了。

代码 (Python)

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
import bisect
import math

class Golomb:
    def __init__(self, MAXN):
        self.MAXN = MAXN
        self.optim2(MAXN)

    def query(self, n):
        k = bisect.bisect_left(self.T, n)
        return self.S[k - 1] + math.ceil((n - self.T[k - 1]) / k)

    def optim2(self, n):
        self.G = [0] * (n + 1)
        self.G[1] = 1
        self.G[2] = 2
        self.S = [0] * (n + 1)
        self.S[1] = 1
        self.T = [0] * (n + 1)
        self.T[1] = 1
        i = j = 2
        while i <= n and j <= n:
            for _ in range(self.G[i]):
                self.G[j] = i
                self.S[j] = self.S[j - 1] + self.G[j]
                self.T[j] = self.T[j - 1] + j * self.G[j]
                j += 1
                if j > n:
                    break
            i += 1


if __name__ == "__main__":
    MAXN = int(1e6)
    golomb = Golomb(MAXN)

    for i in range(1, 30):
        print("{}: {}".format(i, golomb.query(i)))

    for i in range(int(1e6), int(1e6) + 30):
        print("{}: {}".format(i, golomb.query(i)))

    for i in range(int(1e9), int(1e9)+30):
        print("{}: {}".format(i, golomb.query(i)))

    for i in range(int(2e15), int(2e15)+30):
        print("{}: {}".format(i, golomb.query(i)))

通过引入 $T$，即可在只预处理到 $1e6$ 的情况下，即可在 $O(\log(1e6))$ 下响应 $2e15$ 级别的查询。

提交代码

在洛谷题目链接 P8676 [蓝桥杯 2018 国 A] 自描述序列 中，提交上述优化2的代码：

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
import bisect
import math

class Golomb:
    def __init__(self, MAXN):
        self.MAXN = MAXN
        self.optim2(MAXN)

    def query(self, n):
        k = bisect.bisect_left(self.T, n)
        return self.S[k - 1] + math.ceil((n - self.T[k - 1]) / k)

    def optim2(self, n):
        self.G = [0] * (n + 1)
        self.G[1] = 1
        self.G[2] = 2
        self.S = [0] * (n + 1)
        self.S[1] = 1
        self.T = [0] * (n + 1)
        self.T[1] = 1
        i = j = 2
        while i <= n and j <= n:
            for _ in range(self.G[i]):
                self.G[j] = i
                self.S[j] = self.S[j - 1] + self.G[j]
                self.T[j] = self.T[j - 1] + j * self.G[j]
                j += 1
                if j > n:
                    break
            i += 1


if __name__ == "__main__":
    MAXN = int(1e6)
    golomb = Golomb(MAXN)

    n = int(input())
    print(golomb.query(n))
Share