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";
}