Description：

求出一个字符串所有子串的 $AABB$ 拆分的总方案数。

$1\leqslant n\leqslant 30000$

Solution：

首先我们要求一个 $st[i]$ 表示以 $i$ 位置为开头的 $AA$ 拆分的方案数， $ed[i]$ 是以 $i$ 结尾，那么答案就是 $\begin{align}\sum_{i=1}^{n-1}ed[i]\times st[i+1]\end{align}$ ，问题就变成了怎么求 $AA$ ，首先可以 $O(n^2)$ 哈希暴力，这样可以得到 $95$ 分，正解的做法比较神奇，先枚举划分长度 $l$ ，然后每 $l$ 划分一段，那么一个 $AA$ 一定会跨过至少 $2$ 段，也就是说如果 $LCS(i,i+l)+LCP(i+1,i+l+1)\geqslant l$ 的话就找到了一些 $AA$ ，发现他们一定是连续的，于是在一个数组上差分统计即可，求 $LCS$ 和 $LCP$ 可以对正串和反串分别求后缀数组然后用 $ST$ 表 $O(1)$ 回答询问，时间复杂度由调和级数得是 $O(n\ln n)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 30010

char s1[MAXN],s2[MAXN];

int n;

int sa1[MAXN],rnk1[MAXN],height1[MAXN];

int sa2[MAXN],rnk2[MAXN],height2[MAXN];

int t1[MAXN],t2[MAXN],c[MAXN];

void make_SA(char s[],int n,int m,int sa[],int rnk[],int height[])

{

	memset(t1,0,sizeof(t1));

	memset(t2,0,sizeof(t2));

	int *x = t1,*y = t2;

	int p;

	for(int i = 1;i <= m;++i)c[i] = 0;

	for(int i = 1;i <= n;++i)++c[x[i] = s[i]];

	for(int i = 1;i <= m;++i)c[i] += c[i - 1];

	for(int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

	for(int k = 1;k <= n;k = k << 1)

	{

		p = 0;

		for(int i = n - k + 1;i <= n;++i)y[++p] = i;

		for(int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

		for(int i = 1;i <= m;++i)c[i] = 0;

		for(int i = 1;i <= n;++i)++c[x[y[i]]];

		for(int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		p = 1;

		swap(x,y);x[sa[1]] = 1;

		for(int i = 2;i <= n;++i)

		{

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		}

		if(p >= n)break;

		m = p;

	}

	for(int i = 1;i <= n;++i)

	{

		rnk[sa[i]] = i;

	}

	int k = 0;

	for(int i = 1;i <= n;++i)

	{

		if(rnk[i] == 1)continue;

		if(k)--k;

		int j = sa[rnk[i] - 1];

		while(j + k <= n && s[i + k] == s[j + k])++k;

		height[rnk[i]] = k;

	}

	return;

}

int st[MAXN],ed[MAXN];

int f1[MAXN][20],f2[MAXN][20];

int LCP(int x,int y)

{

	if(x == y)return n - x + 1;

	x = rnk1[x];y = rnk1[y];

	if(x > y)swap(x,y);

	++x;

	int l = log2(y - x + 1);

	return min(f1[x][l],f1[y - (1 << l) + 1][l]);

}

int LCS(int x,int y)

{

	if(x == y)return x;

	x = n - x + 1;y = n - y + 1;

	x = rnk2[x];y = rnk2[y];

	if(x > y)swap(x,y);

	++x;

	int l = log2(y - x + 1);

	return min(f2[x][l],f2[y - (1 << l) + 1][l]);

}

void add(int s[],int l,int r)

{

	s[l] += 1;s[r + 1] -= 1;

	return;

}

void work()

{

	memset(st,0,sizeof(st));

	memset(ed,0,sizeof(ed));

	memset(height1,0,sizeof(height1));

	memset(height2,0,sizeof(height2));

	memset(rnk1,0,sizeof(rnk1));

	memset(rnk2,0,sizeof(rnk2));

	memset(sa1,0,sizeof(sa1));

	memset(sa2,0,sizeof(sa2));

	memset(f1,0,sizeof(f1));

	memset(f2,0,sizeof(f2));

	memset(s1,0,sizeof(s1));

	memset(s2,0,sizeof(s2));

	scanf("%s",s1 + 1);

	n = strlen(s1 + 1);

	for(int i = 1;i <= n;++i)s2[i] = s1[n - i + 1];

	make_SA(s1,n,256,sa1,rnk1,height1);

	make_SA(s2,n,256,sa2,rnk2,height2);

	for(int i = 1;i <= n;++i)f1[i][0] = height1[i];

	for(int i = 1;i <= n;++i)f2[i][0] = height2[i];

	for(int k = 1;k <= 19;++k)

		for(int i = 1;i <= n - (1 << k) + 1;++i)

			f1[i][k] = min(f1[i][k - 1],f1[i + (1 << (k - 1))][k - 1]);

	for(int k = 1;k <= 19;++k)

		for(int i = 1;i <= n - (1 << k) + 1;++i)

			f2[i][k] = min(f2[i][k - 1],f2[i + (1 << (k - 1))][k - 1]);

	for(int i = 1;i <= n - 1;++i)

	{

		if(s1[i] == s1[i + 1])

		{

			add(st,i,i);

			add(ed,i + 1,i + 1);

		}

	}

	for(int l = 2;l <= n;++l)

	{

		for(int i = l;i <= n - l;i += l)

		{

			if(LCS(i,i + l) <= 0)continue;

			if(LCS(i,i + l) > 0 && LCP(i + 1,i + l + 1) + LCS(i,i + l) >= l)

			{

				int L = i - LCS(i,i + l) + 1;

				if(L <= i - l + 1)L = i - l + 1;

				int R = i + LCP(i + 1,i + l + 1) - l + 1;

				if(R >= i)R = i;

				add(st,L,R);

				add(ed,L + l * 2 - 1,R + l * 2 - 1);

			}

		}

	}

	for(int i = 1;i <= n;++i)st[i] += st[i - 1];

	for(int i = 1;i <= n;++i)ed[i] += ed[i - 1];

	long long ans = 0;

	for(int i = 1;i < n;++i)

	{

		ans += ed[i] * st[i + 1];

	}

	cout << ans << endl;

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}