rt. 不是满分做法，但是 wa 的是什么回事

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn=(1<<20)+5;
const ll pbits=1145141923;
int n;
ll ans=0;
char s[maxn];
ll _hash[maxn];
int record[maxn];

ll quickpow(ll x,ll y){
	ll ans=1;
	while(y!=0){
		if(y&1) ans*=x;
		x*=x;
		y>>=1;
	}
	return ans;
}

struct node{
	int ltcnt[35];
}t[maxn];
int t2[35];
int lowbit(int x){return x&-x;}
void update(int x,int val){
	for(;x<=26;x+=lowbit(x)){
		t2[x]+=val;
	}
}
int query(int x){
	int res=0;
	for(;x>=1;x-=lowbit(x)){
		res+=t2[x];
	}
	return res;
}

int cnt[35],ccnt[maxn][35],cfcnt[maxn][35];
void init(){
	ans=0;
	memset(t2,0,sizeof t2);
	for(int j=1;j<=26;++j) cnt[j]=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=26;++j) ccnt[i][j]=cfcnt[i][j]=0;
	}
}
void calclen(){
	for(int i=1;i<=n;++i){
		_hash[i]=_hash[i-1]*pbits+s[i];
		t[i]=t[i-1];
		++t[i].ltcnt[s[i]-96];//计算1~i中每种字符出现次数
	}
	
	for(int len=1;len<=n;++len){
		ll standard=_hash[len];
		record[len]=1;
		for(int st=len+1;st<=n;st+=len){
			int en=st+len-1;
			if(en>=n) break;
			if(_hash[en]-_hash[st-1]*quickpow(pbits,en-st+1)!=standard){
				break;
			}
			++record[len];//求AB组合长度为len时，最多能往后排多少个
		}
	}
	for(int len=1;len<=n;++len){
		for(int o=1;o<=26;++o){
			cfcnt[len][o]=t[n].ltcnt[o]-t[(record[len]-1)*len].ltcnt[o];//AB组合，长度为len，当AB排列最长时，C每种字符的数量
		}
		for(int o=1;o<=26;++o){
			ccnt[len][o]=t[n].ltcnt[o]-t[record[len]*len].ltcnt[o];
//AB组合，长度为len，当AB排列次长时，C每种字符的数量
		}
	}
}
int main(){
//	freopen("string4.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		
		init();
		calclen();
		
		int aprimes=0;
		for(int len=2;len<=n-1;++len){
			++cnt[s[len-1]-96];
			if(cnt[s[len-1]-96]&1) ++aprimes;
			else --aprimes;
			update(aprimes+1,1);
			//树状数组，长度为len时，多一种情况，为前len-1个字符为A，最后一个单独为B
			int cprimes1=0,cprimes2=0;//不要介意变量名是primes :(
			for(int o=1;o<=26;++o){
				if(ccnt[len][o]&1) ++cprimes1;
				if((cfcnt[len][o]&1)&&record[len]>1) ++cprimes2;
			}
			if(record[len]==1) cprimes2=cprimes1;//不存在次长
			ans+=1ll*record[len]*query(min(cprimes1,cprimes2)+1);
			if(cprimes1<cprimes2){
				ans+=1ll*(query(cprimes2+1)-query(cprimes1+1))*record[len]/2;
			}
			else ans+=1ll*(query(cprimes1+1)-query(cprimes2+1))*(record[len]+1)/2;
		}
		printf("%lld\n",ans);
	}
    return 0;
}

下面是原先的 48pts 暴力代码，除ac外只有tle

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn=(1<<20)+5;
const ll pbits=1145141923;
int n;
ll ans=0;
char s[maxn];
ll _hash[maxn];
int record[maxn];

ll quickpow(ll x,ll y){
	ll ans=1;
	while(y!=0){
		if(y&1) ans*=x;
		x*=x;
		y>>=1;
	}
	return ans;
}

int cnt[30],ccnt[maxn][30],cfcnt[maxn][30];
void init(){
	ans=0;
	for(int j=1;j<=26;++j) cnt[j]=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=26;++j) ccnt[i][j]=cfcnt[i][j]=0;
	}
}
void calclen(){
	for(int i=1;i<=n;++i){
		_hash[i]=_hash[i-1]*pbits+s[i];
	}
	
	for(int len=1;len<=n;++len){
		ll standard=_hash[len];
		record[len]=1;
		for(int st=len+1;st<=n;st+=len){
			int en=st+len-1;
			if(en>=n) break;
			if(_hash[en]-_hash[st-1]*quickpow(pbits,en-st+1)!=standard){
				break;
			}
			++record[len];
		}
	}
	for(int len=1;len<=n;++len){
		for(int j=(record[len]-1)*len+1;j<=record[len]*len;++j){
			++cfcnt[len][s[j]-96];
		}
		for(int j=record[len]*len+1;j<=n;++j){
			++ccnt[len][s[j]-96];
			++cfcnt[len][s[j]-96];
		}
	}
}
int main(){
//	freopen("string4.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		
		init();
		calclen();
		
		int aprimes=0;
		for(int sla=1;sla<=n-2;++sla){//A的长度
			++cnt[s[sla]-96];
			if(cnt[s[sla]-96]&1) ++aprimes;
			else --aprimes;
			for(int len=sla+1;len<=n-1;++len){//AB一起的长度
				int cprimes1=0,cprimes2=0;
				for(int o=1;o<=26;++o){
					if(ccnt[len][o]&1) ++cprimes1;
					if(cfcnt[len][o]&1) ++cprimes2;
				}
				//以上只有两种情况，1：ABABABAB_C_，2：ABABAB_ABC_,C再吞并，奇数字符数也是这两种之一
				if(aprimes<=cprimes1&&aprimes<=cprimes2) ans+=record[len];
				else if(aprimes<=cprimes1&&aprimes>cprimes2) ans+=(record[len]+1)/2;
				else if(aprimes>cprimes1&&aprimes<=cprimes2) ans+=record[len]/2;
			}
		}
		printf("%lld\n",ans);
	}
    return 0;
}

感觉像是树状数组出锅了，求调谢谢