题解

题目理解

我们需要在一条长度为 $n$ 的颜色链子中，找出所有满足特定条件的"漂亮连续片段"。一个片段被认为是漂亮的，当且仅当：

• 包含恰好 $l_1$ 个颜色 $c_1$、$l_2$ 个颜色 $c_2$、...、$l_m$ 个颜色 $c_m$
• 不包含任何其他颜色的链环

关键难点

直接统计每个片段中各种颜色的数量会非常耗时，时间复杂度为 $O(n \times m)$，在 $n, m$ 达到 $10^6$ 时无法接受。

算法思路

核心思想：哈希编码

为每个颜色分配一个唯一的哈希值，然后用哈希值的加权和来表示颜色组合。

具体步骤：

1. 预处理哈希基数

   hsh[0] = 1;
   for (int i = 1; i <= n; i++)
       hsh[i] = hsh[i - 1] * base % mod;
   

   这里使用 $base^i$ 作为颜色 $i$ 的哈希值，确保不同颜色的哈希值线性无关。

2. 计算目标哈希值

   for (int i = 1, x; i <= m; i++) {
       scanf("%lld", &x);
       res += hsh[x] * l[i] % mod;
       res %= mod;
   }
   

   计算漂亮片段的"目标哈希值"：$res = \sum_{i=1}^m hsh[c_i] \times l_i$

3. 构建前缀哈希和

   for (int i = 1, x; i <= n; i++) {
       scanf("%lld", &x);
       sum[i] = (sum[i - 1] + hsh[x]) % mod;
   }
   

   计算链子的前缀哈希和，便于快速计算任意区间的哈希和。

4. 滑动窗口检查

   for (int i = 1; i + len - 1 <= n; i++) {
       ans += ((sum[i + len - 1] - sum[i - 1] + mod) % mod == res);
   }
   

   对于每个长度为 $len$ 的窗口，检查区间 $[i, i+len-1]$ 的哈希和是否等于目标哈希值。

算法正确性分析

为什么哈希和相等就能保证颜色组合正确？

假设有两个不同的颜色组合：

• 组合A：颜色 $c_1$ 出现 $l_1$ 次，颜色 $c_2$ 出现 $l_2$ 次，...
• 组合B：颜色 $c_1$ 出现 $l_1'$ 次，颜色 $c_2$ 出现 $l_2'$ 次，...

如果它们的哈希和相等：

$$\sum hsh[c_i] \times l_i = \sum hsh[c_i] \times l_i' $$

由于我们使用 $base^i$ 作为颜色 $i$ 的哈希值，这相当于：

$$\sum base^{c_i} \times l_i = \sum base^{c_i} \times l_i' $$

在模 $10^9+7$ 的大质数下，不同幂次的线性组合相等的概率极低（除非组合完全相同），这保证了算法的正确性。

时间复杂度分析

• 预处理：$O(n)$
• 计算目标哈希值：$O(m)$
• 构建前缀和：$O(n)$
• 滑动窗口检查：$O(n)$

总时间复杂度：$O(n)$，完美处理 $n = 10^6$ 的数据规模。

代码细节说明

// 防止负数取模
(sum[i + len - 1] - sum[i - 1] + mod) % mod

这里加上 mod 再取模是为了防止减法产生负数。

样例验证

以题目样例为例：

输入：
7 3
2 1 1
1 2 3
4 2 1 3 1 2 5

计算：
目标哈希值 = hsh[1]*2 + hsh[2]*1 + hsh[3]*1
检查每个长度为4的窗口，找到2个匹配

总结

这种哈希方法巧妙地将复杂的颜色计数问题转化为简单的数值比较问题，通过数学方法在 $O(n)$ 时间内解决了原本需要 $O(nm)$ 的问题，是处理大规模字符串/序列匹配问题的经典技巧。