题解

题目类型：字符串哈希 / 枚举分块 / 数组周期性分析
关键算法：Rolling Hash（字符串哈希） + 枚举子段长度 + 去重计数

一、题意概述

输入一个长度为 len 的整数序列 V（元素可视为字符或数字），要求对每个可能的分段长度 i（1 ≤ i ≤ len）：

• 把整个序列按长度 i 拆分成若干个连续片段；
• 对每个片段求其哈希值与其反转哈希值（即正反向都算）；
• 统计这些哈希值中不同的种类数；
• 找到能使不同片段种类数最多的 i，并输出：
  • 最大的不同片段种类数；
  • 能达到这一最大值的所有 i。

二、主要思路

1. Rolling Hash 原理

定义哈希函数： [ H[i] = (H[i-1] \times base + s[i]) \bmod mod ] 用于快速求任意子段 [l,r] 的哈希值： [ get_hash(l,r) = (H[r] - H[l-1] \times base^{r-l+1}) \bmod mod ] 同时预处理反向哈希 rehash[i]，支持常数时间判断某段是否为回文或取反段值。

2. 分块与去重计数

对每个 i ∈ [1, len]：

• 从 1 开始每次跳步长 i，形成区间 [l = j, r = j+i-1]；
• 若 r > len 则舍弃（不完整块）；
• 计算该区间的正向哈希 hs1 = get_hash(l, r)；
• 计算反向哈希 hs2 = get_rehash(l, r)；
• 将 hs1 与 hs2 都加入一个 map / unordered_map； 若该哈希值之前出现过则跳过，反之计数 cnt++；
• 统计本轮 i 的唯一块数 cnt。

3. 记录最优结果

• 若 cnt > mx，更新 mx = cnt 并清空 vec 保存当前的 i；
• 若 cnt == mx，把该 i 也加入 vec。

最后输出：

mx vec.size()
所有 vec[i]

三、关键细节说明

1. 哈希封装类 String

   • 支持从 string 或 vector<int> 构造；
   • 自动计算正反哈希与 Pow 幂表；
   • 提供多种功能函数：
     • get_hash(l,r)：正向子串哈希；
     • get_rehash(l,r)：反向子串哈希；
     • ishw()：判断整体是否为回文；
     • find_cnt()、find_pos()、mx_xh() 等为通用字符串操作（此题未直接使用）。

2. 正反哈希去重的意义

   • 对称性：若题目允许片段正反视作同类，则哈希与反哈希同时计入可以避免遗漏；
   • 因为序列可能存在“反向等价”的片段，例如 [1,2,3] 与 [3,2,1]。

3. 优化

   • 若 len / i < mx 说明即使所有块都不重复也不会超过当前最优值，可直接剪枝退出；
   • 复杂度约为 O(len * sqrt(len)) ~ O(len log len)，对 len ≤ 2e6 仍可接受。

四、复杂度分析

• 时间复杂度：
  枚举长度 i（最多 len 次），每次约 len / i 段；
  哈希 O(1)，插入去重 O(1~log n)，整体近似
  [ O(len \log len) ]
• 空间复杂度：
  维护哈希表、Pow 表等，O(len)。

五、样例推演（思路示例）

若输入序列 V = [1,2,1,2,1,2]：

• 当 i=1：块为 [1][2][1][2][1][2]，有两种不同数字 → cnt=2
• 当 i=2：块 [1,2][1,2][1,2] → 只有一种 [1,2] → cnt=1
• 当 i=3：块 [1,2,1][2,1,2] → 两种不同 → cnt=2 → 最大 cnt=2，对应 i=1,3。

输出：

2 2
1 3

六、完整代码（与题目代码一致）

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct String {
  const int base = 360004823, mod = 1e9 + 7;
  string sss;
  int len;
  long long Pow[2000010], hash[2000010], rehash[2000010];
  String(string s) {
    Pow[0] = 1;
    hash[0] = 0;
    sss = s;
    len = s.length();
    rehash[len + 1] = 0;
    for (int i = 1; i <= len; i++) Pow[i] = Pow[i - 1] * base % mod;
    for (int i = 1; i <= len; i++)
      hash[i] = (hash[i - 1] * base + s[i - 1]) % mod;
    for (int i = len; i >= 1; i--)
      rehash[i] = (rehash[i + 1] * base + s[i - 1]) % mod;
  }
  String(vector<int> s) {
    Pow[0] = 1;
    hash[0] = 0;
    len = s.size();
    rehash[len + 1] = 0;
    for (int i = 1; i <= len; i++) Pow[i] = Pow[i - 1] * base % mod;
    for (int i = 1; i <= len; i++)
      hash[i] = (hash[i - 1] * base + s[i - 1]) % mod;
    for (int i = len; i >= 1; i--)
      rehash[i] = (rehash[i + 1] * base + s[i - 1]) % mod;
  }
  int get_hash(int l, int r) {
    if (r < l) return 0;
    return (((hash[r] - hash[l - 1] * Pow[r - l + 1]) % mod + mod) % mod);
  }
  inline int get_rehash(int l, int r) {
    if (r < l) return 0;
    return (((rehash[l] - rehash[r + 1] * Pow[r - l + 1]) % mod + mod) % mod);
  }
};
void Luo_Saisei() {
  int len;
  cin >> len;
  vector<int> V(len);
  for (auto &x : V) cin >> x;
  String S(V);
  vector<int> vec;
  int mx = 0;
  for (int i = 1; i <= len; i++) {
    if (len / i < mx) break;
    map<int, int> mp;
    int cnt = 0;
    for (int j = 1; j <= len; j += i) {
      int l = j, r = j + i - 1;
      if (r > len) continue;
      int hs1 = S.get_hash(l, r);
      int hs2 = S.get_rehash(l, r);
      if (mp.count(hs1) || mp.count(hs2)) continue;
      mp[hs1] = 1;
      mp[hs2] = 1;
      cnt++;
    }
    if (cnt > mx) {
      vec.clear();
      vec.push_back(i);
      mx = cnt;
    } else if (cnt == mx)
      vec.push_back(i);
  }
  cout << mx << ' ' << vec.size() << '\n';
  for (auto x : vec) cout << x << ' ';
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  Luo_Saisei();
}