If we enumerate $C$and use the KMP algorithm to calculate the minimum loop section, the complexity $\Theta (Tn \sqrt n)$of the factor of the loop section length for each enumeration can be 84 points, which is sufficient for the NOIP first prize.

But the exact solution is not difficult either. We find that when enumerating factors, many enumerations are meaningless. We are considering a different approach. Enumeration $AB$, then enumerate the number of loops, and the remaining segment is $C$. For odd occurrences of characters, prefixes and techniques can be used to maintain them. The overall complexity is $\ Theta (n\ln n)$. The natural logarithm comes from harmonic series.

#include<bits/stdc++.h>
#define int long long
#define uint unsigned long long
using namespace std;
const int N=1048577,B=131;
int T,n,ans;
string s;
uint ha[N],fac[N];
int cnt[26],suf[N];
int pre_cnt[27];
inline int getha(int l,int r) {
	return ha[r]-ha[l-1]*fac[r-l+1];
}
signed main() {
	std::ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--) {
		cin>>s;
		n=s.size();
		s=" "+s;
		fac[0]=1,ans=0;
		for(int i=1; i<=n; ++i) {
			fac[i]=fac[i-1]*B;
			ha[i]=ha[i-1]*B+s[i];
		}
		memset(cnt,0,sizeof cnt);
		for(int i=n,nw=0; i>=1; --i) {
			++cnt[s[i]-'a'];
			if(cnt[s[i]-'a']&1)++nw;
			else --nw;
			suf[i]=nw;
		}
		memset(cnt,0,sizeof cnt);
		memset(pre_cnt,0,sizeof pre_cnt);
		for(int i=1,nw=0; i<=n; ++i) {
			if(i>=2) {
				for(int j=1; j*i<n; ++j) {
					if(getha(1,i)==getha(1+(j-1)*i,j*i)) {
						ans+=pre_cnt[suf[j*i+1]];
					} else break;
				}
			}
			++cnt[s[i]-'a'];
			if(cnt[s[i]-'a']&1)++nw;
			else --nw;
			for(int j=0; j<=26; ++j) {
				if(j>=nw) ++pre_cnt[j];
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

考场上的思路是考虑枚举 $C$ 的长度，然后计算合法的 $A$ 和 $B$ ，然而这并不可行

所以我们考虑枚举 $AB$ 整个的长度，然后只要是循环节我们就累加答案，否则就退出

枚举 $AB$ 然后判断是否为循环节可以使用哈希完成

然后对于出现奇数次数的字母显然可以使用桶来计算出来，然后我们需要使用一个二维数组 $a_{i,j}$ 表示前 $i$ 个字符为 $A$ ，且出现奇数次数字母的前缀个数 $\leq j$ 的数量，然后就做完了

但是可能需要卡常，不要把所有东西都开成long long，哈希使用unsigned long long

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define P 13331
#define uint unsigned long long
using namespace std;
bool Test_MLE_start;
const int N=(1<<20)+10;
int _=1,n,a[N][27];long long ans=0;
short ton[30],cnt[N],suf[N];
uint h[N],fac[N];char s[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
}
inline void clr(){
//	Don't forget!
	ans=0;
	for(int i=1;i<=n;i++){
		h[i]=suf[i]=cnt[i]=0;
		for(int j=0;j<=26;j++) a[i][j]=0,ton[j]=0;
	}
}
uint get_ha(int L,int R){return h[R]-h[L-1]*fac[R-L+1];}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
	_=reads();
	while(_--){
		clr();scanf("%s",s+1);n=strlen(s+1);fac[0]=1;
		for(int i=1;i<=n;i++){
			h[i]=h[i-1]*P+s[i],fac[i]=fac[i-1]*P;
			ton[s[i]-'a'+1]++;
			for(int j=1;j<=26;j++){
				if(ton[j]&1) cnt[i]++;
			}a[i][cnt[i]]++;
			for(int j=0;j<=26;j++) a[i][j]+=a[i-1][j];
		}for(int i=1;i<=n;i++){
			for(int j=1;j<=26;j++) a[i][j]+=a[i][j-1];
		}memset(ton,0,sizeof(ton));
		for(int i=n;i>=1;i--){
			ton[s[i]-'a'+1]++;
			for(int j=1;j<=26;j++){
				if(ton[j]&1) suf[i]++;
			}
		}for(int len=2;len<=n;len++){
			for(int i=len+1;i<=n;i+=len){
				ans+=a[len-1][suf[i]];
				if(get_ha(1,len)!=get_ha(i,i+len-1)) break;
			}
		}printf("%lld\n",ans);
	}
	return 0;
}
/*
1
mmlmmlo
*/```

考場上的思路是考慮枚舉$C$的長度，然後計算合法的$A$和$B$，然而這並不可行 所以我們考慮枚舉$AB$整個的長度，然後只要是迴圈節我們就累加答案，否則就退出

枚舉$AB$然後判斷是否為迴圈節可以使用雜湊完成

然後對於出現奇數次數的字母顯然可以使用桶來計算出來，然後我們需要使用一個二維陣列$a_{i，j}$表示前$i$個字元為$A$，且出現奇數次數字母的首碼個數$\leq j$的數量，然後就做完了

但是可能需要卡常，不要把所有東西都開成long long，雜湊使用unsigned long long

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define P 13331
#define uint unsigned long long
using namespace std;
bool Test_MLE_start;
const int N=(1<<20)+10;
int _=1,n,a[N][27];long long ans=0;
short ton[30],cnt[N],suf[N];
uint h[N],fac[N];char s[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
}
inline void clr(){
//	Don't forget!
	ans=0;
	for(int i=1;i<=n;i++){
		h[i]=suf[i]=cnt[i]=0;
		for(int j=0;j<=26;j++) a[i][j]=0,ton[j]=0;
	}
}
uint get_ha(int L,int R){return h[R]-h[L-1]*fac[R-L+1];}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
	_=reads();
	while(_--){
		clr();scanf("%s",s+1);n=strlen(s+1);fac[0]=1;
		for(int i=1;i<=n;i++){
			h[i]=h[i-1]*P+s[i],fac[i]=fac[i-1]*P;
			ton[s[i]-'a'+1]++;
			for(int j=1;j<=26;j++){
				if(ton[j]&1) cnt[i]++;
			}a[i][cnt[i]]++;
			for(int j=0;j<=26;j++) a[i][j]+=a[i-1][j];
		}for(int i=1;i<=n;i++){
			for(int j=1;j<=26;j++) a[i][j]+=a[i][j-1];
		}memset(ton,0,sizeof(ton));
		for(int i=n;i>=1;i--){
			ton[s[i]-'a'+1]++;
			for(int j=1;j<=26;j++){
				if(ton[j]&1) suf[i]++;
			}
		}for(int len=2;len<=n;len++){
			for(int i=len+1;i<=n;i+=len){
				ans+=a[len-1][suf[i]];
				if(get_ha(1,len)!=get_ha(i,i+len-1)) break;
			}
		}printf("%lld\n",ans);
	}
	return 0;
}
/*
1
mmlmmlo
*/```

The idea in the exam room is to enumerate the length of $C$and then calculate the valid $A$and $B$, but this is not feasible

So we consider enumerating the entire length of $AB$, and then accumulating the answers as long as it is a loop section, otherwise we exit

List $AB$and determine if it is a cyclic section that can be completed using hashing

Then, for letters with an odd number of occurrences, buckets can be used to calculate them. We need to use a two-dimensional array $a_ {i, j}$to represent the first $i$characters as $A$and the number of prefixes $\leq j$for letters with an odd number of occurrences. That's it

But it may need to be stuck, don't open everything as' long long ', use' unsigned long long 'for hashing`

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define P 13331
#define uint unsigned long long
using namespace std;
bool Test_MLE_start;
const int N=(1<<20)+10;
int _=1,n,a[N][27];long long ans=0;
short ton[30],cnt[N],suf[N];
uint h[N],fac[N];char s[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
}
inline void clr(){
//	Don't forget!
	ans=0;
	for(int i=1;i<=n;i++){
		h[i]=suf[i]=cnt[i]=0;
		for(int j=0;j<=26;j++) a[i][j]=0,ton[j]=0;
	}
}
uint get_ha(int L,int R){return h[R]-h[L-1]*fac[R-L+1];}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
	_=reads();
	while(_--){
		clr();scanf("%s",s+1);n=strlen(s+1);fac[0]=1;
		for(int i=1;i<=n;i++){
			h[i]=h[i-1]*P+s[i],fac[i]=fac[i-1]*P;
			ton[s[i]-'a'+1]++;
			for(int j=1;j<=26;j++){
				if(ton[j]&1) cnt[i]++;
			}a[i][cnt[i]]++;
			for(int j=0;j<=26;j++) a[i][j]+=a[i-1][j];
		}for(int i=1;i<=n;i++){
			for(int j=1;j<=26;j++) a[i][j]+=a[i][j-1];
		}memset(ton,0,sizeof(ton));
		for(int i=n;i>=1;i--){
			ton[s[i]-'a'+1]++;
			for(int j=1;j<=26;j++){
				if(ton[j]&1) suf[i]++;
			}
		}for(int len=2;len<=n;len++){
			for(int i=len+1;i<=n;i+=len){
				ans+=a[len-1][suf[i]];
				if(get_ha(1,len)!=get_ha(i,i+len-1)) break;
			}
		}printf("%lld\n",ans);
	}
	return 0;
}
/*
1
mmlmmlo
*/```