rt，复杂度是 $O(n \ln n + 26 n)$

int n;
string s;
ull hs[N], pw[N];
vector<int> con[N];
vector<int> pre[27], suf[27];
int b[N], c[N], sum[N];
int cnt[26];
ull get(int l, int r) {
	return hs[r] - hs[l - 1] * pw[r - l + 1];
}

void solve() {
	cin >> s;
	n = s.size();
	s = " " + s;
	for (int i = 1; i <= n; i ++) {
		con[i].clear();
		c[i] = 0;
	}
	for (int i = 1; i <= n; i ++) {
		hs[i] = hs[i - 1] * P + s[i] - 'a' + 1;
	}
	for (int len = 1; len <= n; len ++) {
		for (int i = 1; i <= n; i += len) {
			int j = i + len - 1;
			if (get(i, j) == hs[len]) {
				con[j].push_back(len);
			} else {
				break;
			}
		}
	}
	for (int i = 0; i < 26; i ++) {
		cnt[i] = 0;
	}
	for (int i = 0; i <= 26; i ++) {
		pre[i].clear(), suf[i].clear();
	}
	int cur = 0;
	for (int i = 1; i <= n; i ++) {
		cur -= cnt[s[i] - 'a'];
		cnt[s[i] - 'a'] ^= 1;
		cur += cnt[s[i] - 'a'];
		pre[cur].push_back(i);
	}
	for (int i = 0; i < 26; i ++) {
		cnt[i] = 0;
	}
	cur = 0;
	for (int i = n; i >= 1; i --) {
		cur -= cnt[s[i] - 'a'];
		cnt[s[i] - 'a'] ^= 1;
		cur += cnt[s[i] - 'a'];
		suf[cur].push_back(i);
	}

	ll ans = 0;
	for (int f = 0; f <= 26; f ++) {
		for (int i = 1; i <= n; i ++) {
			b[i] = 0;
		}
		for (auto i : pre[f]) {
			b[i + 1] ++;
		}
		for (int i = 1; i <= n; i ++) {
			b[i] += b[i - 1];
			c[i] += b[i];
		}
		for (auto i : suf[f]) {
			for (auto j : con[i - 1]) {
				ans += c[j];
			}
		}
	}
	cout << ans << "\n";
}