【XSY3333】魔力（差分，哈希）

”每个字符出现次数相等“ 可以使用差分简化：记录数组 \(s_c\) 为字符 \(c\) 的出现次数减去字符 \(\texttt{"a"}\) 的出现次数，那么条件等价于 \(s\) 数组全为 \(0\)。

维护 \(s\) 数组的前缀和，那么就是要找 \((i,j)\) 使得 \(i\) 处的 \(s\) 的前缀和和 \(j\) 处的 \(s\) 的前缀和相等。

哈希即可。

#include<bits/stdc++.h>

#define N 100010
#define fi first
#define se second
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)

using namespace std;

namespace modular
{
	const int mod1=1000000007,mod2=19260817,mod3=998244353;
	inline int add(int x,int y,const int &mod){return x+y>=mod?x+y-mod:x+y;}
	inline int dec(int x,int y,const int &mod){return x-y<0?x-y+mod:x-y;}
	inline int mul(int x,int y,const int &mod){return 1ll*x*y%mod;}
}using namespace modular;

const int base2=23333,base3=1145141;
int Sd2,bit2[52];
int Sd3,bit3[52];

int n,a[N];
int idx,id[100];
pii sum[N];
int ans;
bool vis[100];
char s[N];

pii get(pii x,int c,bool opt)
{
	if(!c) return opt?mk(dec(x.fi,Sd2,mod2),dec(x.se,Sd3,mod3)):mk(add(x.fi,Sd2,mod2),add(x.se,Sd3,mod3));
	return opt?mk(add(x.fi,bit2[c-1],mod2),add(x.se,bit3[c-1],mod3)):mk(dec(x.fi,bit2[c-1],mod2),dec(x.se,bit3[c-1],mod3));
}

map<pii,int>val;

int main()
{
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;i++)
	{
		a[i]=s[i]-'A';
		vis[a[i]]=1;
	}
	for(int i=0;i<100;i++)
		if(vis[i]) id[i]=idx++;
	if(idx==1)
	{
		printf("%d\n",(int)((1ll*n*(n+1)/2)%mod1));
		return 0;
	}
	bit2[0]=Sd2=1;
	bit3[0]=Sd3=1;
	for(int i=1;i<idx-1;i++)
	{
		bit2[i]=mul(bit2[i-1],base2,mod2);
		Sd2=add(Sd2,bit2[i],mod2);
		bit3[i]=mul(bit3[i-1],base3,mod3);
		Sd3=add(Sd3,bit3[i],mod3);
	}
	sum[0]=mk(0,0);
	val[mk(0,0)]++;
	for(int i=1;i<=n;i++)
	{
		sum[i]=get(sum[i-1],id[a[i]],1);
		ans=add(ans,val[sum[i]],mod1);
		val[sum[i]]++;
	}
	printf("%d\n",ans);
	return 0;
}
/*
8
abccbabc
*/
/*
7
abcABCC
*/
/*
13
aabbabababbab
*/