我的思路就是先枚举哪一段是 $C$，然后 hash 判前面循环节。但是只有 60。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int t,n,c[26],cnt,sum[1100010][27];
long long ans;
string s;
const unsigned long long base=130;
unsigned long long h[1100010],power[1100010];
unsigned long long hs(int l,int r){
	return h[r]-h[l-1]*power[r-l+1];
}
void pre()
{
	for(int i=1;i<=n;i++)
		h[i]=h[i-1]*base+s[i];
	for(int i=1;i<=n;i++)
	{
		int x=s[i]-'a';
		c[x]++;
		if(c[x]%2)cnt++;
		else cnt--;
		for(int j=0;j<=26;j++)
			sum[i][j]=sum[i-1][j]+(cnt==j);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=26;j++)
			sum[i][j]+=sum[i][j-1];
}
bool chk(int x,int len){
	return hs(1,x-len)==hs(len+1,x);
}
int main()
{
	cin>>t;
	power[0]=1;
	for(int i=1;i<=1100000;i++)power[i]=power[i-1]*base;
	while(t--)
	{
		memset(c,0,sizeof(c));
		memset(sum,0,sizeof(sum));
		cnt=0;
		cin>>s;
		n=s.size();
		s=' '+s;
		pre();
		// for(int i=1;i<=n;i++)
		// {
		// 	for(int j=0;j<=4;j++)cout<<sum[i][j]<<" ";cout<<endl;
		// }
		memset(c,0,sizeof(c));
		cnt=0,ans=0;
		for(int i=n;i>=3;i--)
		{
			int x=s[i]-'a';
			c[x]++;
			if(c[x]%2)cnt++;
			else cnt--;
			for(int len=1;len*len<i;len++)
				if((i-1)%len==0)
				{
					if(chk(i-1,len))
					{
						//cout<<i-1<<" "<<len<<" "<<sum[len-1][cnt]<<endl;
						ans+=sum[len-1][cnt];
					}
					if(len*len<i-1&&chk(i-1,(i-1)/len))
					{
						//cout<<i-1<<" "<<(i-1)/len<<" "<<sum[(i-1)/len-1][cnt]<<endl;
						ans+=sum[(i-1)/len-1][cnt];
					}
				}
		}
		cout<<ans<<endl;
	}
	return 0;
}