「一本通 2.1 练习 5」Beads

形式化题目

给定长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 与正整数 $k$ 。按从左到右、每 $k$ 个元素一组切分，得到 $m = \lfloor n/k \rfloor$ 个块

B_1 = (a_1, \dots, a_k),\quad B_2 = (a_{k+1}, \dots, a_{2k}),\quad \dots,\quad B_m = (a_{(m-1)k+1}, \dots, a_{mk}),

末尾不足 $k$ 个元素的部分直接丢弃。规定块的反转与原块等价：块 $x$ 与它的反转 $x^{R}$ 视为同一个块。

记 $\mathrm{cnt}(k)$ 为这 $m$ 个块在"反转等价"下的不同块数。求

\mathrm{best} = \max_{1 \leqslant k \leqslant n} \mathrm{cnt}(k), \qquad K = \{\, k \mid \mathrm{cnt}(k) = \mathrm{best} \,\},

并输出 $\mathrm{best}$ 、 $|K|$ 以及 $K$ 中所有元素（升序）。

正解

思路

朴素做法的瓶颈在哪里

对每个 $k$ ，把 $\lfloor n/k \rfloor$ 个块放进集合去重，去重时把块和它的反转当作同一元素。块的总数是

\sum_{k=1}^{n} \left\lfloor \frac{n}{k} \right\rfloor \approx n \ln n = O(n \log n),

$n = 200000$ 时约 $2.4 \times 10^6$ 块。这个规模本身没问题，问题出在单个块的处理不是 $O(1)$ ：

若逐字符与其他块比较，单块最坏 $O(n)$ ，整体退化到 $O(n ^ 2 \log n)$ ；
若把块存成 tuple 并用 min(t, t[::-1]) 去重，t[::-1] 要复制 $O(k)$ 个元素，实测 $n = 200000$ 时约 166 秒。

所以要做的是：给每个块一个定长的整数指纹，让单块编码降到 $O(1)$ 。

滚动哈希： $O(1)$ 取块的指纹

先做三项 $O(n)$ 预处理（下列式子都在模 $2^{64}$ 意义下）：

幂表 $pw[i] = B^{i}$ ；
正向前缀哈希 $pre[i] = a_1 B^{i-1} + a_2 B^{i-2} + \dots + a_i$ ；
反向前缀哈希 $suf[i] = a_n B^{\,n-i} + a_{n-1} B^{\,n-i-1} + \dots + a_i$ 。

于是位置 $p$ 起、长度 $k$ 的块

\text{fwd}(p,k) = pre[p+k] - pre[p] \cdot B^{k}, \qquad \text{bwd}(p,k) = suf[p] - suf[p+k] \cdot B^{k}

都可以在 $O(1)$ 内算出。

关键观察： $\text{bwd}$ 就是反转块的正读哈希

$suf[p] - suf[p+k] B^k$ 展开后的指数从 $k-1$ 递减到 $0$ ，对应的序列是

a_{p+k-1},\ a_{p+k-2},\ \dots,\ a_p,

正好是把块 $(a_p, \dots, a_{p+k-1})$ 颠倒过来之后的正读哈希。也就是说，我们不需要真的构造反转数组，反向表天然给出了它。

设块为 $x$ 、其反转为 $x^{R}$ ，则

\text{fwd}_x = \text{bwd}_{x^{R}}, \qquad \text{bwd}_x = \text{fwd}_{x^{R}},

两个指纹在反转下互换。因此定义

\text{code}(x) = \min(\text{fwd}_x,\ \text{bwd}_x),

就有 $\text{code}(x) = \text{code}(x^{R})$ ——反转等价被自动合并进同一个整数。把它当集合键，len(set(...)) 就是这个 $k$ 的不同块数。

为什么用 $2^{64}$ 而不是大素数

素数取模需要真正的取余运算，CPython 对 60 位以上整数的 % 开销明显。改用 $2^{64}$ 后所有取模变成 & ((1 << 64) - 1)，实测把最坏用例从 1.05 s 压到 0.74 s，这正是本解能压进 1000 ms 的关键。可行性依赖两点：

底数 $B$ 取奇数（ $B = 1000003$ ），与 $2^{64}$ 互素，于是 $B^{k}$ 在环 $Z_{2^{64}}$ 中可逆，区间还原公式仍然成立；
减法可能得到负数，& MASK 等价于"加 $2^{64}$ 再取模"，结果正确。

下面的表格是样例在 $k=2$ 时的实际指纹，可以看到第 5 块 $(2,3)$ 与第 10 块 $(3,2)$ 尽管顺序相反，却得到相同的 code，因此只算一个不同块。

起点 $p$	块	$\text{fwd}$	$\text{bwd}$	$\text{code}=\min$
0	`(1,1)`	1000004	1000004	1000004
2	`(1,2)`	1000005	2000007	1000005
4	`(2,2)`	2000008	2000008	2000008
6	`(3,3)`	3000012	3000012	3000012
8	`(3,1)`	3000010	1000006	1000006
10	`(2,3)`	2000009	3000011	2000009
12	`(3,1)`	3000010	1000006	1000006
14	`(2,2)`	2000008	2000008	2000008
16	`(1,3)`	1000006	3000010	1000006
18	`(3,2)`	3000011	2000009	2000009

表中 10 个块只产生 6 种不同的 code，与样例所说的 $k=2$ 有 6 个不同子串一致；其中 (3,1)、(1,3) 共享 1000006，(2,3)、(3,2) 共享 2000009。

算法主干

graph TD
    A["读入 n 与序列 a"] --> B["预处理 pw / pre / suf，均为 O(n)"]
    B --> C["k 从 1 枚举到 n"]
    C --> D["对每个完整块起点 p = 0, k, 2k, ...<br/>O(1) 算出 code = min(fwd, bwd)"]
    D --> E["len(set(codes)) 即为 cnt(k)"]
    E --> F{"cnt(k) 与 best 比较"}
    F -->|更大| G["best = cnt(k)，ks 重置为 [k]"]
    F -->|相等| H["ks 追加 k"]
    F -->|更小| I["跳过"]
    G --> J{"k 枚举完?"}
    H --> J
    I --> J
    J -->|否| C
    J -->|是| K["输出 best、len(ks) 与 ks 中所有 k"]

每轮只做 $\lfloor n/k \rfloor$ 次 $O(1)$ 编码，总编码次数 $O(n \log n)$ 。

代码

Python 版：

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
48
49#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 12:10
# update_at: 2026-09-30 12:10

import sys

MASK = (1 << 64) - 1  # 取模用位与代替 %：底数为奇数时 2^64 取模仍是合法滚动哈希
BASE = 1_000_003      # 奇数底数，保证块哈希能用前缀哈希 O(1) 还原


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]

    # 幂表、正向前缀哈希、反向（从右往左）前缀哈希，三张表都是 O(n) 预处理
    pw = [1] * (n + 1)
    pre = [0] * (n + 1)   # pre[i] = a[0..i-1] 的哈希
    suf = [0] * (n + 1)   # suf[i] = a[i..n-1] 的哈希（越靠左权重越高）
    for i in range(1, n + 1):
        pw[i] = (pw[i - 1] * BASE) & MASK
    for i, x in enumerate(a):
        pre[i + 1] = (pre[i] * BASE + x) & MASK
    for i in range(n - 1, -1, -1):
        suf[i] = (suf[i + 1] * BASE + a[i]) & MASK

    best, ks = 0, []
    for k in range(1, n + 1):
        wk = pw[k]
        # 每 k 个珠子的块取一次（末尾不足 k 的丢弃）；正读与倒读哈希取小者，
        # 于是 (1,2,3) 与 (3,2,1) 落到同一个编码，去重后即为不同子串数
        cnt = len({
            min((pre[p + k] - pre[p] * wk) & MASK, (suf[p] - suf[p + k] * wk) & MASK)
            for p in range(0, n - k + 1, k)
        })
        if cnt > best:
            best, ks = cnt, [k]
        elif cnt == best:
            ks.append(k)

    print(best, len(ks))
    print(' '.join(map(str, ks)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 02:40
 * update_at: 2026-10-05 02:40
 */
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 200005;

// 正反两向滚动哈希，2^64 自然溢出等价于模 2^64，底数取奇数保证可逆
typedef unsigned long long ull;

const ull BASE = 1000003ULL; // 奇数底数，B^k 在模 2^64 下可逆

ll n;                          // 珠子个数
ll a[MAXN];                    // a[i] 为第 i 个珠子的颜色（下标从 1 开始）
ull pw[MAXN];                  // pw[i] = BASE^i
ull pre[MAXN];                 // pre[i] = a[1..i] 的正向哈希
ull suf[MAXN];                 // suf[i] = a[i..n] 的反向哈希（越靠左权重越高）
ull block_code[MAXN];          // 当前 k 下每个完整块的编码（正读、倒读哈希取小）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 三张预处理表都是 O(n)
    pw[0] = 1ULL;
    for (ll i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * BASE;
    }
    pre[0] = 0ULL;
    for (ll i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] * BASE + a[i];
    }
    suf[n + 1] = 0ULL;
    for (ll i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] * BASE + a[i];
    }

    ll best = -1;        // 目前找到的最大不同块数
    vector<ll> ks;       // 取得最大值的所有 k（升序）

    for (ll k = 1; k <= n; k++) {
        ll m = n / k;    // 完整块个数，末尾不足 k 的珠子丢弃

        // 每个块用正读哈希 fwd 与倒读哈希 bwd 的较小者作为编码；
        // 块与其反转的编码相同，于是同一个编码只算一个不同块
        for (ll idx = 0; idx < m; idx++) {
            ll p = idx * k + 1;                          // 块起点（1-based）
            ull fwd = pre[p + k - 1] - pre[p - 1] * pw[k];
            ull bwd = suf[p] - suf[p + k] * pw[k];
            block_code[idx] = fwd < bwd ? fwd : bwd;
        }

        // 排序后统计不同编码个数，即为 cnt(k)
        sort(block_code, block_code + m);
        ll cnt = 0;
        for (ll idx = 0; idx < m; idx++) {
            if (idx == 0 || block_code[idx] != block_code[idx - 1]) {
                cnt++;
            }
        }

        if (cnt > best) {
            best = cnt;
            ks.clear();
            ks.push_back(k);
        } else if (cnt == best) {
            ks.push_back(k);
        }
    }

    cout << best << ' ' << ks.size() << '\n';
    for (size_t i = 0; i < ks.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << ks[i];
    }
    cout << '\n';

    return 0;
}

复杂度

时间：预处理 $O(n)$ ，枚举 $k$ 的总编码次数 $\sum_{k=1}^{n} \lfloor n/k \rfloor = O(n \log n)$ ，故 $O(n \log n)$ 。
空间：三张长度 $n+1$ 的表，加上单个 $k$ 的哈希集合， $O(n)$ 。

与数据仓里 OI 官方的替代解 kor2.cpp（正反双向哈希 + 排序去重）同阶，优于 kor.cpp 的后缀数组解法 $O(n \log^2 n)$ 。

总结

本题的规模瓶颈是"块的总数 $O(n \log n)$ 还能接受，但单块处理必须 $O(1)$ "。
正反两向前缀哈希让"块"和"块的反转"都能在 $O(1)$ 内取到指纹；再对两个指纹取 $\min$ ，就把"反转视为相同"编码进了同一个整数。
Python 侧用 $2^{64}$ 取模配合位与 & MASK（底数取奇数以保证可逆）压掉取模开销，最坏用例从 1.05 s 降到 0.74 s，实测 32 组官方数据在 1000 ms / 128 MB 内全部通过。