题目链接：NOI2016 优秀的拆分
（刷新以获取数学公式）
题意
如果一个字符串可以被拆分为 \(AABB\) 的形式，其中 \(A\) 和 \(B\)是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 \(aabaabaa\)，如果令 \(A=aab\)，\(B=a\)，我们就找到了这个字符串拆分成 \(AABB\) 的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 \(A=a\)，\(B=baa\)，也可以用 \(AABB\) 表示出上述字符串；但是，字符串 \(abaabaa\) 就没有优秀的拆分。
现在给出一个长度为 \(n\) 的字符串 \(S\)，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
- 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
- 在一个拆分中，允许出现 \(A=B\)。例如 \(cccc\) 存在拆分 \(A=B=c\)。
- 字符串本身也是它的一个子串。
数据范围 ： \(n≤30000,T≤10\)
题解
设\(f_{i}\)为以\(i\)结尾的\(AA\)串数目，\(g_i\)为以\(i\)开头的 \(AA\)串数目，那么答案就是\(\sum_{i}f_ig_{i+1}\)
考虑对每一个长度\(len\)计算对\(f,g\)的贡献。
先枚举一个\(len\)，将串切成\(\lceil \frac{n}{len} \rceil\)段，除了最后一段外，所有段都要求长度是\(len\)，假设第\(i\)段与第\(i+1\)段的\(lcs\)长度为\(a\)，第\(i+1\)段与第\(i+2\)段\(lcp\)长度为\(b\)，那么就有\(\max\{0,a+b-len\}\)个位置可以放下一个\(AA\)串，其中\(A\)的长度是\(len\)。
求串\(S[x-l+1..x]\)和\(S[y-l+1..y]\)的\(lcp\)：\(O(1)\)定位到节点\(S[1..x]\)和\(S[1..y]\)，利用\(ST\)表\(O(1)\)求出两者在\(Parent\)树上的\(LCA\)，那么答案就是\(\min\{mx[lca], l\}\)，其中\(mx\)是一个结点对应最长串的长度。由于预处理\(ST\)表和枚举\(len\)时的调和级数，总复杂度就是\(O(nlogn)\)
#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
struct SAM {
int tot, rt, las, tim;
int nod[N], pre[N], len[N], dep[N], st[N][17], ch[N][26];
int dfn[N << 1], pos[N << 1], Log[N << 1];
vector<int> son[N];
void init() {
tim = 0;
for (int i = 1; i <= tot; ++i) {
pre[i] = len[i] = dep[i] = nod[i] = 0;
memset(st[i], 0, sizeof st[i]);
memset(ch[i], 0, sizeof ch[i]);
son[i].clear();
}
tot = rt = las = 1;
}
int newnode(int l) {
++tot;
len[tot] = l;
return tot;
}
void ins(int c, int x) {
int p = las, np = las = newnode(len[p] + 1);
nod[x] = np;
while (!ch[p][c]) ch[p][c] = np, p = pre[p];
if (!p) pre[np] = rt;
else {
int q = ch[p][c], nq;
if (len[p] + 1 == len[q]) pre[np] = q;
else {
nq = newnode(len[p] + 1);
memcpy(ch[nq], ch[q], sizeof ch[q]);
pre[nq] = pre[q]; pre[q] = pre[np] = nq;
while (ch[p][c] == q) ch[p][c] = nq, p = pre[p];
}
}
}
void dfs(int x) {
dfn[++tim] = x;
pos[x] = tim;
dep[x] = dep[pre[x]] + 1;
for (int i = 0; i < son[x].size(); ++i) {
dfs(son[x][i]);
dfn[++tim] = x;
}
}
int _min(int x, int y) {
return dep[x] < dep[y] ? x : y;
}
void prework() {
for (int i = 2; i <= tot; ++i) {
son[pre[i]].push_back(i);
}
dfs(rt);
for (int i = 2; i <= tim; ++i) {
Log[i] = Log[i >> 1] + 1;
}
for (int i = 1; i <= tim; ++i) {
st[i][0] = dfn[i];
}
for (int j = 1; j <= 16; ++j) {
for (int i = 1; i + (1 << j) - 1 <= tim; ++i) {
st[i][j] = _min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
}
}
int lca(int x, int y) {
x = pos[x]; y = pos[y];
if (x > y) swap(x, y);
int len = Log[y - x + 1];
return _min(st[x][len], st[y - (1 << len) + 1][len]);
}
int lcs(int x, int y, int l, int n) {
int p = lca(nod[x], nod[y]);
return min(l, len[p]);
}
}sam1, sam2;
int n;
int f[N], g[N];
char s[N];
void solve() {
scanf("%s", s + 1);
sam1.init();
sam2.init();
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) f[i] = g[i] = 0;
for (int i = 1; i <= n; ++i) sam1.ins(s[i] - 'a', i);
for (int i = 1; i <= n; ++i) sam2.ins(s[n - i + 1] - 'a', i);
sam1.prework();
sam2.prework();
for (int len = 1; len <= n; ++len) {
for (int i = 1; i + len * 2 - 1 <= n; i += len) {
int j = i + len;
int lcs = sam1.lcs(i + len - 1, j + len - 1, len, n);
int lcp = sam2.lcs(n + 1 - (i + len), n + 1 - (j + len), len - 1, n);
if (lcs + lcp < len) continue;
++f[i + len * 3 - lcs - 1]; --f[i + lcp + len * 2];
++g[i + len - lcs]; --g[i + lcp + 1];
}
}
for (int i = 1; i <= n; ++i) {
f[i] += f[i - 1];
g[i] += g[i - 1];
}
long long ans = 0;
for (int i = 1; i < n; ++i) {
ans += 1LL * f[i] * g[i + 1];
}
cout << ans << endl;
}
int main() {
int T;
cin >> T;
while (T--) solve();
return 0;
}