2017 年欧洲信息学奥林匹克竞赛 Day1 Problem A
很好的题目。
题意简述
给一个长度为 \(n\) 的字符串，字符集为 \(\Sigma\)，求这个字符串含有 \(|\Sigma|\) 个不同字母的子串的数量。
好久没见到这样的好题了。
我们发现正解对我这样的蒟蒻有些困难，于是考虑随机化+哈希。
以下令 \(t=|\Sigma|\)。
我们对字符集内 \(t\) 种字符赋上 \(t\) 种值，使得 \(t\) 个数的和为 \(0\)，否则和不为 \(0\)。
然后瞬间难度降级，我们需要统计有多少个区间映射的值的和为 \(0\)。
这很套路，我们做一个前缀和，把枚举到某个位置得到的和记到桶 \(p\) 里面，最后答案为：
\[\sum \frac{p_i\times(p_i-1)}{2}
\]
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
bool cnt[300];
int tot;
char c[100];
int t[300];
map<int,int> p;
signed main(){int n;cin>>n;string s;cin>>s;for(int i=0;i<n;i++) {if(!cnt[s[i]]) {cnt[s[i]]=1;c[++tot]=s[i];}} //为字母映射一个值 srand(time(0));srand(rand());int sum=0;for(int i=1;i<=tot/2;i++) {int x=rand()*rand()*rand();t[c[i]]=-x;sum+=t[c[i]];}for(int i=tot/2+1;i<=tot-1;i++) {int y=rand()*rand()*rand();t[c[i]]=y;sum+=t[c[i]];}t[c[tot]]=(0-sum);
// for(int i=1;i<=tot;i++) {
// cout<<c[i]<<" ";
// cout<<t[c[i]]<<"\n";
// }p[0]=1;sum=0;for(int i=0;i<n;i++) {sum+=t[s[i]];p[sum]++;}int ans=0;for(auto i:p) {int tmp=1ll*i.second*(i.second-1ll)/2ll%mod;ans=(ans+tmp)%mod;}cout<<ans;return 0;
}