分析

规定以下讨论中，字符串的下标从 \(1\) 开始。

注意到 \((AB)^K\) 一定是一段前缀，\(C\) 一定是一段后缀，而 \(AB\) 又一定是 \((AB)^k\) 的前缀，且满足连续出现 \(k\) 次。

考虑 \(S\) 的 \(z\) 函数。

如果知道了 \(AB\) 的长度和 \(k\)，那么就能计算出对应的 \(C\)。设当前 \(AB\) 长度为 \(i\)，那么最多的循环次数为 \[ \lfloor \frac{z_{i+1}}{i} \rfloor + 1 \] 感性理解一下，显然是对的。

当然这是“至多”，我们可以规定循环次数为任何一个小于最多次数，大于 \(0\) 的整数。

注意到对于奇偶性相同的 \(k\)，出现次数为奇数的字符个数是相等的，所以只需要分奇偶讨论。当 \(k\) 为奇数时，个数不变，当 \(k\) 为偶数时，不存在出现次数为奇数的字符。

设 \(g(l,r)\) 为 \(S[l,r]\) 中出现次数为奇数的字符的数量。设当前 \(AB\) 长度为 \(i\)，\(|A| = j\)。

首先一定存在 \(F(A) \le F(C)\)，\(F(A) = g(1,j)\)。

• 如果 \(k\) 是个奇数，那么就有 \(g(1,j) \le g(i+1,n)\)。尽管 \(C\) 中具体有多少个出现次数为奇数的字符是未知的，但是 \((AB)^k\) 在 \([i+1,n]\) 的出现次数一定为偶数次，所以不会产生影响，\(g(i+1,n)\) 就是 \(F(C)\)。
• 否则，由于 \((AB)^k\) 不存在这类字符，所以 \([1,ki]\) 就不存在出现次数为奇数的字符，因此 \(F(C) = g(ki+1,n) = g(1,n) \Longrightarrow g(1,j) \le g(1,n)\)。

如何维护这类信息？使用树状数组。设 \(C(x)\) 表示长度小于 \(i\) 且这类字符的个数小于等于 \(x\) 的前缀的数量。

同时用变量 \(pre\) 表示 \([1,i]\) 中这类字符的个数，\(suf\) 表示 \([i+1,n]\) 中的，\(all\) 表示 \(g(1,n)\)。

对于 \(t = \lfloor \frac{z_{i+1}}{i} \rfloor + 1\)，奇数的情况有 \(t - \lfloor \frac{t}{2} \rfloor\)，偶数则有 \(\lfloor \frac{t}{2} \rfloor\)。对于 \(i\) \[ (t - \lfloor \frac{t}{2} \rfloor) \cdot C(suf) + \lfloor \frac{t}{2} \rfloor \cdot C(all) \] 然后插入 \(pre\) 即可。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=(1<<20)+2;
int t, n, z[N], p[30], q[30], c[30];
char s[N];
void modify(int x,int y) { for(;x<=27;x+=x&-x) c[x]+=y; }
int query(int x) {
	int y=0;
	for(;x;x-=x&-x) y+=c[x];
	return y;
}
void Z() {
	int l=0, r=0;
	z[0]=n;
	for(int i=1;i<n;++i) {
		if(i<=r&&z[i-l]<r-i+1) z[i]=z[i-l];
		else {
			z[i]=max(r-i+1,0ll);
			while(i+z[i]<n&&s[z[i]]==s[i+z[i]]) ++z[i];
			if(r<i+z[i]-1) l=i, r=i+z[i]-1;
		}
	}
	for(int i=0;i<n;++i) if(i+z[i]==n) --z[i];
    // 由于c不是空串，所以i+z[i]必须小于n
}
void solve() {
	scanf("%s",s);
	n=strlen(s);
	memset(c,0,sizeof(c));
	memset(p,0,sizeof(p));
	memset(q,0,sizeof(q));
	Z();
	int ans=0, pre=0, suf=0;
	for(int i=0;i<n;++i) ++q[s[i]-'a'];
	for(int i=0;i<26;++i) if(q[i]&1) ++suf;
	int all=suf;
	for(int i=0;i<n-1;++i) {
		int d=s[i]-'a';
		++p[d], --q[d];
		if(p[d]&1) ++pre; else --pre;
		if(q[d]&1) ++suf; else --suf;
		if(i) {
			int t=z[i+1]/(i+1)+1;
            // 由于我的代码中i从0开始，所以要+1表示长度为i，和z[i+1]中的+1无关
			ans+=(t-t/2)*query(suf+1)+(t/2)*query(all+1);
            // 为了防止0下标，这些都要+1
		}
		modify(pre+1,1);
	}
	printf("%lld\n",ans);
}
signed main() {
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	t=read();
	while(t--) solve();
}