思路与算法

枚举AB的长度p。设前缀奇偶掩码为mask[p]，全文为mask[n]。用Z数组求前缀AB能连续重复的最大次数K=min(⌊(n-1)/p⌋,1+⌊Z[p]/p⌋)。C非空使上界为n-1。i为奇数时，C掩码是mask[n]异或mask[p]；i为偶数时是mask[n]。因此只需分别统计奇数i、偶数i的个数。随p增长，将A长度1..p-1的F(A)加入大小27的树状数组，查询F(A)≤F(C)的数量，乘对应重复次数并求和。

正确性说明

固定p和i后，C由末尾位置唯一确定，A可以是AB前缀中的任意非空真前缀，B随之唯一确定。Z数组保证且仅保证i个AB与原串前缀一致，长度限制保证C非空。重复偶数次的字符奇偶贡献全抵消，重复奇数次与一个AB相同，故两类C条件推导成立。树状数组恰维护所有可能A的奇数出现字符数，因此计数没有遗漏或重复。不同p、i或A长度产生不同三元组。

复杂度

设串长n、字母表σ=26。读串、Z与奇偶前缀初始化O(n)，每个p进行树状数组更新和两次查询O(log(σ+1))，总O(n log(σ+1))时间、O(n+σ)空间。各组工作量求和。

易错点

A、B、C必须均非空，p从2到n-1；n<3答案0。掩码位异或而非计数相加。方案数与乘法使用64位；i的奇偶数量分别为(K+1)/2、K/2。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
    int t[28] = {};
    void add(int x) {
        for (++x; x < 28; x += x & -x)
            t[x]++;
    }
    int get(int x) {
        int s = 0;
        for (++x; x; x -= x & -x)
            s += t[x];
        return s;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int n = s.size();
        vector<int> z(n), mask(n + 1);
        for (int i = 1, l = 0, r = 0; i < n; i++) {
            if (i <= r)
                z[i] = min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]])
                z[i]++;
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        for (int i = 0; i < n; i++)
            mask[i + 1] = mask[i] ^ (1 << (s[i] - 'a'));
        Fenwick bit;
        long long ans = 0;
        for (int p = 2; p < n; p++) {
            bit.add(__builtin_popcount((unsigned)mask[p - 1]));
            int k = min((n - 1) / p, 1 + z[p] / p);
            int odd = __builtin_popcount((unsigned)(mask[n] ^ mask[p]));
            int even = __builtin_popcount((unsigned)mask[n]);
            ans += 1LL * ((k + 1) / 2) * bit.get(odd) + 1LL * (k / 2) * bit.get(even);
        }
        cout << ans << '\n';
    }
}