题意回顾

给定长度为 $N$ 的字符串，统计有多少个子串是"有魔力的"：

• 设整个字符串有 $K$ 种不同字符
• 一个子串是"有魔力的"当且仅当：该子串包含全部 $K$ 种字符，且每种字符出现次数相同
• 不同位置但内容相同的子串算作不同的子串

数据范围：$N \le 10^5$

关键转化

1. 必要条件分析

设子串长度为 $L$，则条件等价于：

• 子串包含全部 $K$ 种字符
• 每种字符出现次数 $= L / K$（必须是整数）

因此 $L$ 必须是 $K$ 的倍数。

2. 前缀和表示

对每种字符 $c$，定义前缀和数组： [ \text{pref}_c[i] = \text{前 } i \text{ 个字符中字符 } c \text{ 的出现次数} ]

对于子串 $s[l..r]$，字符 $c$ 的出现次数为： [ \text{pref}_c[r] - \text{pref}_c[l-1] ]

条件要求对所有字符 $c$： [ \text{pref}_c[r] - \text{pref}_c[l-1] = \frac{r-l+1}{K} ]

3. 差分技巧

定义差分数组： [ \text{diff}_c[i] = \text{pref}_c[i] - \frac{i}{K} ]

则条件变为： [ \text{diff}_c[r] = \text{diff}_c[l-1] \quad \text{对所有字符 } c ]

这意味着状态向量 $(\text{diff}_{c_1}, \text{diff}_{c_2}, \dots, \text{diff}_{c_K})$ 在位置 $l-1$ 和 $r$ 处必须完全相同。

4. 哈希状态向量

我们可以把整个状态向量哈希成一个值： [ \text{state}[i] = \text{hash}(\text{diff}{c_1}[i], \text{diff}{c_2}[i], \dots, \text{diff}_{c_K}[i]) ]

问题转化为：对于每个 $r$，找到前面有多少个 $l-1$ 满足：

1. $\text{state}[l-1] = \text{state}[r]$
2. 子串 $s[l..r]$ 包含全部 $K$ 种字符

算法实现

步骤 1：预处理

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int BASE = 131;
const int MAXN = 1e5 + 5;

int n;
string s;
map<char, int> char_to_id;
vector<int> char_cnt;  // 每种字符的总出现次数
int K;  // 不同字符种类数

// 获取字符ID
int get_id(char c) {
    if (!char_to_id.count(c)) {
        char_to_id[c] = K++;
        char_cnt.push_back(0);
    }
    return char_to_id[c];
}

步骤 2：计算状态向量和哈希

vector<vector<int>> pref;  // pref[c][i]: 字符c在前i个位置的出现次数
vector<vector<double>> diff;  // diff[c][i] = pref[c][i] - i/K

// 计算状态哈希
ll get_state_hash(int pos) {
    ll hash_val = 0;
    for (int c = 0; c < K; c++) {
        // 由于浮点数精度问题，实际用整数处理
        // diff[c][pos] = K*pref[c][pos] - pos
        ll val = (ll)K * pref[c][pos] - pos;
        hash_val = hash_val * BASE + val;
    }
    return hash_val;
}

步骤 3：滑动窗口验证字符集完整性

我们需要确保子串包含全部 $K$ 种字符。可以用滑动窗口维护当前窗口内的字符集。

int count_magic_substrings() {
    // 预处理前缀和
    pref.assign(K, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        int c_id = get_id(s[i-1]);
        for (int c = 0; c < K; c++) {
            pref[c][i] = pref[c][i-1] + (c == c_id);
        }
    }
    
    // 计算状态哈希
    vector<ll> state(n + 1);
    for (int i = 0; i <= n; i++) {
        state[i] = get_state_hash(i);
    }
    
    // 统计答案
    ll ans = 0;
    map<ll, vector<int>> state_positions;
    
    // 对于每个可能的子串长度 L (必须是K的倍数)
    for (int L = K; L <= n; L += K) {
        state_positions.clear();
        
        // 滑动窗口维护字符集
        vector<int> window_cnt(K, 0);
        int unique_chars = 0;
        
        for (int r = 1; r <= n; r++) {
            // 添加字符s[r-1]
            int c = get_id(s[r-1]);
            if (window_cnt[c] == 0) unique_chars++;
            window_cnt[c]++;
            
            // 如果窗口大小超过L，移除左边字符
            if (r > L) {
                int left_char = get_id(s[r-L-1]);
                window_cnt[left_char]--;
                if (window_cnt[left_char] == 0) unique_chars--;
            }
            
            // 当窗口大小等于L时检查
            if (r >= L) {
                int l = r - L + 1;
                if (unique_chars == K && state[l-1] == state[r]) {
                    ans++;
                }
            }
        }
    }
    
    return ans % MOD;
}

复杂度分析

• 预处理：$O(nK)$
• 状态哈希：$O(nK)$
• 统计答案：$O(n \log n)$（使用map）

由于 $K \le 52$，总复杂度 $O(nK)$ 可接受。

总结

本题的关键在于：

1. 状态向量表示：用 $\text{diff}_c[i] = \text{pref}_c[i] - \frac{i}{K}$ 转化条件
2. 哈希状态：将高维状态向量压缩为单个哈希值
3. 字符集完整性：用滑动窗口或双指针维护
4. 高效统计：利用哈希表快速查找相同状态的位置对