题目描述

给定一个长度为 的整数数组 和一个正整数 。我们定义一个子数组是“和谐的”，当且仅当：

对于该子数组中出现的每一种数字，其出现次数都是 的倍数（包括 0 次，但子数组非空，故至少有一种数字出现 ≥1 次且为 的倍数）。

你的任务是：统计数组中“和谐的”非空子数组的总数。

本题是前缀哈希 + 异或状态压缩 + 随机化防冲突类型的题目，难度 中等偏上。

核心思路

核心观察

1. 和谐子数组 ⇨ 前缀状态相等
   设 prefix[i] 表示前 个元素（ 到 ）构成的状态。
   若子数组 是和谐的，则对任意数字 ，其在 中的出现次数 ，
   等价于：prefix[r+1] 与 prefix[l] 的状态完全相同。

2. 状态如何表示？

   • 对每个数字 ，记录其当前出现次数模 的值 。
   • 不能直接用全部的 (x, r) 的集合比较（太慢），需压缩为单个哈希值。
   • 使用异或哈希：为每个 分配一个独立随机指纹 ，整体状态为所有 对应指纹的异或和。

3. 状态更新
   当数字 的计数从 变为 时：

   • 先异或掉旧状态：state ^= H(x, r_old)
   • 再异或上新状态：state ^= H(x, r_new)

4. 边界处理

   • 空前缀状态为 0，需初始化 cnt[0] = 1。
   • 若 ，所有子数组都和谐，答案为 。

5. 防冲突

   • 使用 mt19937_64 生成 64 位随机数作为 ，冲突概率极低（）。

算法步骤

1. 对每组测试数据：
   • 特判 ，直接输出结果。
2. 初始化：
   • state = 0
   • states_cnt = {0: 1}（空前缀）
   • num_cnt（记录各数字当前模 计数）
   • H（懒加载存储 ）
3. 遍历数组：
   • 更新当前数字的计数（模 ）
   • 用 get(x, old_r, H) 和 get(x, new_r, H) 获取指纹
   • 更新 state
   • 累加 states_cnt[state] 到答案
   • states_cnt[state]++
4. 输出答案。

正确性分析

• 状态唯一性：每个 有独立随机指纹，不同状态几乎不可能哈希冲突。
• 异或性质：异或满足自反性（），完美匹配“移除旧状态、添加新状态”的需求。
• 前缀相等 ⇨ 子数组和谐：由模 计数差为 0 推出，逻辑严密。
• 懒加载安全：每组测试数据独立重建 H，避免跨组污染。

复杂度分析

• 时间复杂度：

  • 每组数据：
    • 主要开销：map<pair<int,int>, ull> 的每次查询/插入为 ，其中 为不同 对数量。
    • 总操作数 ，故总时间 。
  • 所有测试数据总 ，总时间可接受。

• 空间复杂度：

  • 
    • states_cnt、num_cnt、H 最多存储 个键值对。
    • 符合题目约束。

代码

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//哈希值懒加载函数
ull get(int x,int num,map<pair<int,int>,ull>&H){
    if(num==0)return 0;
    auto key=make_pair(x,num);
    if(H.find(key)!=H.end()){
        return H[key];
    }
    else{
        H[key]=rng();
        return H[key];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 如果 m == 1，所有子数组都和谐
        if (m == 1) {
            cout << 1LL * n * (n + 1) / 2 << '\n';
            continue;
        }
        
        ull states=0;
        unordered_map<ull,int>states_cnt;//状态个数数组
        states_cnt[0]=1;//0状态应该1起
        unordered_map<int,int>num_cnt;//数字出现个数的数组
        map<pair<int,int>,ull>H;
        ull ans=0;

        for(int i=0;i<n;i++){
            int old_cnt=num_cnt[a[i]];
            int new_cnt=(old_cnt+1)%m;
            num_cnt[a[i]]=new_cnt;

            states^=get(a[i],old_cnt,H);//删除旧状态
            states^=get(a[i],new_cnt,H);//加入新状态
            ans+=states_cnt[states];
            states_cnt[states]++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}