看到循环部分 \(AB\)，自然想要去枚举它，并且用哈希。开始想到的是倍增+hash求出最长循环的右端点，复杂度是 \(O(n\log n)\)，结果不好写，没写出来。
我们先思考找到右端点怎么计算贡献。最朴素的，我们再枚举前缀 \(ABAB\cdots AB\)，容易预处理出后缀出现奇数次的字符数量，所以当前贡献即为 \(AB\) 能有多少种分割使得 \(A\) 中出现奇数次的字符数量小于后缀的。看出可以把值域看作一维，树状数组单点插入，前缀和查询即可。
看到题解关于复杂度的一个结论 \(\sum\limits_{i=1}^n\dfrac{n}{i}\approx n\ln n\le n\log n\)。
我们直接枚举比倍增还快，这样代码变简单，复杂度降为 \(O(n(\ln n+\log 26))\)，还是不保险。
我们考虑如何简化贡献的计算，发现对于后缀 \(ABABC\)，它出现奇数次的字符数量和 \(C\) 是一样的；而 \(ABABABC\) 与 \(ABC\) 是一样的。所以我们将后缀分为奇偶两部分，每部分的贡献只需要在树状数组求出的值上乘一个系数（即能出现多少次奇偶相同的）。
复杂度为 \(O(n\ln n+\log 26)\)。
#include <bits/stdc++.h>
typedef long long ll;
int read() {
int x = 0, f = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c)) {
x = (x << 3) + (x << 1) + (c - '0');
c = getchar();
}
return x * f;
}
const ll p = 1331, mod = 13333331;
ll t, n, h[2000010], pw[2000010], suf[2000010], vis[30], ans, c[30];
char s[2000010];
ll hsh(int l, int r) {
return (h[r] - h[l - 1] * pw[r - l + 1] % mod + mod) % mod;
}
ll lowbit(ll x) {
return x & (-x);
}
void update(int x, ll y) {
for(int i = x; i <= 27; i += lowbit(i)) {
c[i] += y;
}
}
ll query(int x) {
ll ret = 0;
for(int i = x; i; i -= lowbit(i)) {
ret += c[i];
}
return ret;
}
void Solve() {
t = read();
pw[0] = 1;
for(int i = 1; i <= 2000000; i++) {
pw[i] = pw[i - 1] * p % mod;
}
while(t--) {
ans = 0;
std::cin >> s + 1;
n = strlen(s + 1);
for(int i = 1; i <= n; i++) {
h[i] = (h[i - 1] * p + s[i]) % mod;
}
int now = 0;
memset(vis, 0, sizeof(vis));
memset(c, 0, sizeof(c));
for(int i = n; i >= 1; i--) {
vis[s[i] - 'a']++;
if(vis[s[i] - 'a'] % 2 == 1) now++;
else now--;
suf[i] = now;
}
memset(vis, 0, sizeof(vis));
now = 0;
for(int i = 1; i < n; i++) {
int r = i;
for(int j = i; j <= n; j += i) {
// std::cout << i << " " << j << " " << h[i] << " " << hsh(j - i + 1, j) << "\n";
if(h[i] != hsh(j - i + 1, j) || j == n) {
break;
}
else r = j;
}
// std::cout << i << " " << r << " ";
int res1 = query(suf[r + 1] + 1), res2 = query(suf[r - i + 1] + 1);
// std::cout << res1 << "\n";
if(i != 1) {
if(r / i == 1) {
ans += res1;
}
else {
if(((r / i) % 2) == 0) {
ans += (r / i / 2) * res1;
}
else ans += (r / i / 2 + 1) * res1;
if(((r / i + 1) % 2) == 0) {
ans += ((r / i + 1) / 2 - 1) * res2;
}
else ans += ((r / i + 1) / 2) * res2;
}
}
// std::cout << r << "\n";
vis[s[i] - 'a']++;
if(vis[s[i] - 'a'] % 2 == 1) now++;
else now--;
update(now + 1, 1);
}
std::cout << ans << "\n";
}
}
int main() {
Solve();
return 0;
}