题解

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

typedef long long ll;
const int maxn = (1 << 20) + 5;
int n;
string s;

typedef unsigned long long ull;
ull C = 131;
ull Hash[maxn], pw[maxn];

// pre[i][j]: 前i个字符的所有前缀，奇数数字数量不超过j的前缀数量。
// pre[i][j] = pre[i-1][j] + 1（若前i个字符的奇数出现次数字符小于等于j)
// pre[i][j] = pre[i-1][j]    （若前i个字符的奇数出现次数字符大于j)
// suf[i]: [i:n] (1-index)的子串，奇数出现数字数量
ll pre[27], suf[maxn];
int mp[26];
void init() {
    int num = 0;
    for (int i = 0; i < 26; i++) mp[i] = 0;
    for (int i = n; i >= 1; i--) {
        mp[s[i - 1] - 'a'] ^= 1;
        if (mp[s[i - 1] - 'a'] == 1) num++; else num--;
        suf[i] = num;
    }
}



// substr(i, len) 与 substr(j, len)是否相同 (1-index)
bool same(int i, int j, int len) {
    ull H1 = Hash[i + len - 1] - Hash[i - 1];
    ull H2 = Hash[j + len - 1] - Hash[j - 1];
    return H1 * pw[j - i] == H2;
}

void solve3() {
    Hash[1] = s[0] - 'a'; // 1-index
    for (int i = 2; i <= n; i++) Hash[i] = Hash[i - 1] + pw[i - 1] * (s[i - 1] - 'a' );

    init(); // 预处理pre和suf

    // 串 "AB"的长度i
    ll ans = 0;
    for (int i = 0; i < 26; i++) mp[i] = pre[i] = 0;
    int num = 0; // 前i个数字的奇数数量
    for (int len = 2; len < n; len++) {
        // 起点: i, [i, i + len - 1] 需要等于 [1, len]
        // [ i + len - 1] 需要小于n
        // 字符串C[i+len:]
        mp[s[len - 2] - 'a'] ^= 1;
        num += mp[s[len - 2] - 'a'] == 1 ? 1 : -1;
        for (int i = num; i <= 26; i++) pre[i]++;
//        for (int i = 0; i <= 10; i++) cout << pre[i] << " \n"[i == 10];
        for (int i = 1; i + len - 1 < n; i += len) {
//            cout << " ? " << i << " " << len << " " << same(i, 1, len) << endl;
            if (!same(1, i, len)) break;
            int limit = suf[i + len]; // 最大奇数数量
//            cout << i << " " << len << " " << limit << " " << pre[limit] << endl;
            ans += pre[limit];
        }

    }
    cout << ans << endl;
}


int main(){
//    freopen("_string/string23.in", "r", stdin);
    ios::sync_with_stdio(0);

//    freopen("stringw.out", "w", stdin);

//    for (int i = 2; i < 1e6; i++) {
//        for (int j = i; j < 1e6; j += i) {
//            dp[j][1] += i / 2;
//            dp[j][0] += (i - 1) / 2;
//        }
//    }
//    int TT = 0;
//    auto start = chrono::high_resolution_clock::now();

    pw[0] = 1;
    for (int i = 1; i < maxn; i++) {
        pw[i] = pw[i - 1] * C;
    }

    int T;
    cin >> T;
    while (T--) {
        cin >> s;
        n = s.size();
        solve3();
//        if (n <= 1000) solve();
//        else if (n <= (1 << 15)) {
//
//            solve2();
//        }
//        else solve3();
    }
//    auto stop = chrono::high_resolution_clock::now();
//    auto duration = chrono::duration_cast<chrono::milliseconds>(stop - start).count();
//
//    cout << duration <<"Ms";

}