P6273[eJOI2017] 魔法 题解
考虑定义\(S_{r_k} = \Sigma_{i = 1}^{r}[s_i = k]\)，那么对于任意一个子串\([l,r]\)，其为有魔法的子串的充要条件为\(S_{c_{r}} - S_{c_{l - 1}}\)对于任意的，在\(s\)中出现了的\(c\)为定值。
任取一个在\(s\)中出现了的字符\(A\)，那么上述充要条件可转换为\(S_{c_{r}} - S_{c_{l - 1}} = S_{A_{r}} - S_{A_{l - 1}}\)对于\(s\)中出现的每个字符\(c\)都成立。
移项，得\(S_{c_{r}} - S_{A_{r}} = S_{c_{l - 1}} - S_{A_{l - 1}}\)
拿一个vector<int>维护\({S_{c_{r}} - S_{A_{r}}|c \in S}\)即可
时间复杂度\(O(nklogn)\)
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;
int cnt1[100010],cnt[266],n,k,now,ans;
string s;
map<vector<int>,int> mp;
vector<int> v;
char a1[100010];
int main()
{
cin >> n >> s;
s = s;
strcpy(a1,s.c_str());
sort(a1,a1 + n);
mp[v = (vector<int>(k = unique(a1,a1 + n) - a1,0))] = 1;
for(int i = 0;i < n;i++) {
if(s[i] != a1[0]) {
v[lower_bound(a1,a1 + k,s[i]) - a1]++;
} else {
for(auto &j:v) {
j--;
}
v[0]++;
}
((ans += mp[v]++) %= (int)(1e9 + 7));
}
cout << ans << "\n";
}