为什么这个 nlog+nsigma 慢飞了

#include<bits/stdc++.h>
using namespace std;
int T, n;
unsigned long long pw[1200005], pww[1200005], h1[1200005], h2[1200005];
int mxe[1200005], ca[1200005][27], buk, tot;
const int b1 = 37, b2 = 101, p1 = 998244353, p2 = 1000000007;
long long ans;
string s;
inline void ini(int N){
	pw[0] = 1;
	for (int i = 1; i <= N; i++)
		pw[i] = pw[i - 1] * b1;
}
inline void ghsh(int N){
	h1[0] = 0;
	for (int i = 1; i <= N; i++)
		h1[i] = (h1[i - 1] + (s[i] - 'a' + 1) * pw[i]);
}
inline bool check(int l, int r, int L, int R){
	if (l > L){
		swap(l, L);
		swap(r, R);
	}
	unsigned long long H1 = (h1[r] - h1[l - 1]) * pw[L - l];
	unsigned long long H3 = h1[R] - h1[L - 1];
	return H1 == H3;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ini(1 << 20);
	cin >> T;
	while (T--){
		cin >> s;
		n = s.size();
		s = " " + s;
		ans = 0;
		ghsh(n);
		for (int i = 1; i <= n; i++){
			tot |= (1 << (s[i] - 'a'));
			mxe[i] = 1;
			for (int d = 2; d * i <= n; d++){
				if (check(1, i, i * (d - 1) + 1, i * d))
					mxe[i] = d;
				else
					break;
			}
		}
		tot = __builtin_popcount(tot);
		buk = 0;
		for (int i = 1; i <= n; i++){
			for (int j = 0; j <= tot; j++)
				ca[i][j] = ca[i - 1][j];
			buk ^= (1 << (s[i] - 'a'));
			for (int j = __builtin_popcount(buk); j <= tot; j++)
				ca[i][j]++;
		}
		buk = 0;
		for (int j = n; j >= 1; j--){
			buk ^= (1 << (s[j] - 'a'));
			for (int tmp = 1; tmp * tmp <= (j - 1); tmp++){
				if ((j - 1) % tmp == 0){
					int i = tmp;
                    if (i * mxe[i] >= j - 1){
    					ans += ca[i - 1][__builtin_popcount(buk)];
    				}
					if (tmp * tmp != (j - 1)){
                        i = (j - 1) / tmp;
                        if (i * mxe[i] >= j - 1){
        					ans += ca[i - 1][__builtin_popcount(buk)];
        				}
                    }
				}
			}
		}
		cout << ans << "\n";
	}
	return 0;
}