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

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

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

哈希即可。

#include

#define N 100010
#define fi first
#define se second
#define pii pair
#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));
}

mapval;

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("%dn",(int)((1ll*n*(n+1)/2)%mod1));
		return 0;
	}
	bit2[0]=Sd2=1;
	bit3[0]=Sd3=1;
	for(int i=1;i