问题分析

我们需要将环形项链切成两个部分，使得：

1. 每个部分非空
2. 每种类型的珠子只能出现在一个部分中

求：

1. 有多少种切割方式
2. 两部分长度差的最小值

关键约束：

• 项链是环形的
• $n \leq 10^6$，需要 $O(n)$ 或 $O(n \log n)$ 算法
• 每种类型至少出现一次

核心思想：异或哈希 + 前缀和

1. 问题转化

将环形问题转化为线性问题：

• 考虑在位置 $i$ 和 $j$ 切割（$i < j$）
• 得到的两个部分：$(i+1 \rightarrow j)$ 和 $(j+1 \rightarrow i)$（环形）

条件：每种类型只能出现在一个部分中

2. 哈希表示

为每种类型的珠子分配一个随机数，用异或操作表示集合：

• 如果某个类型的所有珠子都在同一个部分，它们的异或和为 0
• 如果某个类型的珠子分布在两个部分，异或和不为 0

算法详解

数据结构

const int N = 1e6 + 10;
int n, k, cnt, mx = 1e9;
long long ans;
int lst[N];              // 每种类型最后出现的位置
long long tot[N], val[N];// tot[i]: 类型i的异或和; val[i]: 位置i的哈希值
unordered_map<long long, int> num;  // 哈希值到编号的映射
vector<int> a[N];        // 相同哈希值的位置集合

算法步骤

步骤1：初始化随机哈希值

random_device R;
mt19937 G(R());
long long rnd() {
    return uniform_int_distribution<long long>(1, INF)(G);
}

for (int i = 1, x; i <= n; i++) {
    scanf("%d", &x);
    val[i] = rnd();           // 为位置i分配随机数
    tot[x] ^= val[i];         // 类型x的异或和加上这个珠子
    lst[x] = i;               // 记录类型x最后出现的位置
}

步骤2：处理环形性质

for (int i = 1; i <= k; i++) {
    tot[i] ^= val[lst[i]];    // 将最后出现的珠子从异或和中移除
    val[lst[i]] = tot[i];     // 用类型i的异或和替换该位置的哈希值
}

为什么这样处理？

• 对于每种类型，我们选择最后出现的位置作为"特殊位置"
• 将该位置的哈希值改为整个类型的异或和
• 这样，如果切割后该类型的所有珠子在同一部分，特殊位置的贡献会抵消

步骤3：计算前缀哈希

long long now = 0;
for (int i = 1; i <= n; i++) {
    now ^= val[i];           // 当前位置的前缀异或和
    
    if (!num[now])
        num[now] = ++cnt;    // 为新哈希值分配编号
    
    a[num[now]].push_back(i); // 记录该哈希值出现的位置
}

性质：

• 如果 $now_i = now_j$（$i < j$），那么切割 $(i, j)$ 是合法的
• 因为 $now_j \oplus now_i = \bigoplus_{k=i+1}^j val[k] = 0$，表示区间 $(i+1, j)$ 中每种类型都成对出现

步骤4：统计答案

4.1 计算切割方式数

for (int i = 1; i <= cnt; i++) {
    ans += 1ll * a[i].size() * (a[i].size() - 1) / 2;
}

解释：

• 对于每个哈希值，有 $m$ 个位置满足前缀哈希相同
• 从中任选两个位置 $(i, j)$ 作为切割点都是合法的
• 组合数 $C(m, 2) = \frac{m(m-1)}{2}$

4.2 计算最小长度差

for (int i = 1; i <= cnt; i++) {
    sort(a[i].begin(), a[i].end());
    
    for (int j = 0, k = 0; j < (int)a[i].size(); j++) {
        // 双指针：找到满足条件的k
        while (k < (int)a[i].size() - 1 && a[i][k] - a[i][j] < n / 2)
            mx = min(mx, n - 2 * (a[i][k++] - a[i][j]));
        
        mx = min(mx, abs(n - 2 * (a[i][k] - a[i][j])));
    }
}

长度差计算：

• 切割点 $(i, j)$，区间长度 $len = j - i$
• 两个部分长度：$len$ 和 $n - len$
• 长度差：$|n - 2 \times len|$
• 目标：最小化 $|n - 2 \times len|$

双指针优化：

• 对于每个 $j$，找到最大的 $k$ 使得 $a[i][k] - a[i][j] < n/2$
• 这样 $len$ 最接近 $n/2$，长度差最小

正确性证明

定理1：哈希正确性

使用随机哈希，两个不同的集合碰撞的概率极低（生日悖论）。

定理2：切割合法性

切割 $(i, j)$ 合法 ⇔ 前缀哈希 $now_i = now_j$

证明：

• $now_j \oplus now_i = \bigoplus_{k=i+1}^j val[k]$
• 如果这个值为 0，表示区间 $(i+1, j)$ 中每种类型的珠子都成对出现（包括特殊位置的处理）
• 因此每种类型要么全在区间内，要么全在区间外

定理3：环形处理

将最后出现的珠子的哈希值改为类型的异或和，确保了环形切割的正确性。

复杂度分析

时间复杂度

1. 初始化：$O(n)$
2. 处理环形：$O(k)$
3. 计算前缀哈希：$O(n)$
4. 统计答案：$O(\sum |a[i]| \log |a[i]|)$，最坏 $O(n \log n)$
   • 排序：$O(|a[i]| \log |a[i]|)$
   • 双指针：$O(|a[i]|)$

总复杂度：$O(n \log n)$

空间复杂度

• $O(n)$ 存储数组
• $O(n)$ 哈希表
• $O(n)$ 向量数组

示例分析

样例输入

9 5
2 5 3 2 2 4 1 1 3

执行过程：

1. 为每个位置分配随机哈希值
2. 处理类型：
   • 类型2：最后出现在位置5
   • 类型5：最后出现在位置2
   • 类型3：最后出现在位置9
   • 类型4：最后出现在位置6
   • 类型1：最后出现在位置8
3. 修改特殊位置的哈希值
4. 计算前缀哈希，找到相同哈希的位置
5. 统计：找到4组，计算长度差最小为3

算法优势

1. 高效：$O(n \log n)$ 处理百万数据
2. 巧妙：用异或哈希表示集合
3. 正确：随机化保证正确性概率极高
4. 简洁：核心代码简短

随机化分析

使用 $10^{18}$ 范围内的随机数：

• 碰撞概率：约 $n^2 / 2^{64} \approx 10^{-10}$（可忽略）
• 实际上可以视为确定性算法

总结

本题的核心技巧：

1. 异或哈希：用异或操作表示集合，判断是否成对出现
2. 前缀和：将区间问题转化为端点问题
3. 环形处理：巧妙修改特殊位置处理环形
4. 双指针优化：快速找到最接近 $n/2$ 的区间长度

算法结合了哈希、随机化、双指针等多种技术，高效解决了环形分割问题。