TLE求调

#include<bits/stdc++.h>
using namespace std;

int T, N;
string s;
int mod = 998244353, base = 31;
int p[2000006], f[2000006];
bool cnt[131];
int numE = 0; // ji shu
int nxtnumE[2000006];
long long ans = 0;
int sum[28];

void __init(){
	p[0] = 1;
	for (int i = 1; i <= N; i ++){
		p[i] = (1LL * p[i - 1] * base) % mod;
		f[i] = (1LL * f[i - 1] * base + s[i]) % mod;
	}
}

int query(int l, int r){
	int res = (1LL * f[r] - 1LL * f[l - 1] * p[r - l + 1]) % mod;
	res += mod;
	res %= mod;
	// cout << l << " " << r << " " << res << "\n";
	return res;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
    freopen("../data.out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> T;
	while (T --){
		ans = 0;
		memset(sum, 0, sizeof(sum));
		cin >> s;
		N = s.size();
		s = " " + s;
		__init();
		memset(cnt, 0, sizeof(cnt));
		nxtnumE[N + 1] = 0;
		for (int i = N; i > 1; i --){ // C：[i,N]
			cnt[s[i]] ^= 1;
			if (cnt[s[i]]) nxtnumE[i] = nxtnumE[i + 1] + 1;
			else nxtnumE[i] = nxtnumE[i + 1] - 1;
		}
		memset(cnt, 0, sizeof(cnt));
		numE = 0;
		for (int i = 2; i <= N; i ++){
			cnt[s[i - 1]] ^= 1;
			if (cnt[s[i - 1]]){
				numE ++;
				for (int j = numE; j <= 26; j ++) sum[j] ++;
			}else{
				numE --;
				for (int j = numE; j <= 26; j ++) sum[j] ++;
			}
			for (int j = 1; i * j < N; j ++){ // j duan
				if (query((j - 1) * i + 1, j * i) == query(1, i)){
					ans += sum[nxtnumE[i * j + 1]];
				}else{
					break;
				}
			}
		}
		printf("%lld\n", ans);
	}

    return 0;
}