这题数据有点毒瘤啊……
以后数组大小要开双倍……
首先考虑设 \(a_i\) 表示有多少个以第 \(i\) 个字符结尾的如此 \(AA\) 串，设 \(b_i\) 表示有多少个以第 \(i\) 个字符开头的。
显然答案即 \(\sum\limits_{i = 1}^{n - 1} a_i b_{i + 1}\)。
然鹅作为一道良心题，求 \(a,b\) 暴力哈希就可以 95pts 了……
好的我们讲正解。
考虑枚举 \(AA\) 串的 \(|A|\) 为 \(w\)，我们把每个 \(w | i\) 的下标 \(i\) 都抽出来。
那么任意一个 \(AA(|A| = w)\) 都跨过了相邻的两个这样的下标。
于是我们可以考虑对这些下标算贡献。
考虑相邻的两个点 \(l,r = l + w\)，设 \(lcp\) 为后缀 \(l,r\) 的 LCP 长度，\(lcs\) 为前缀 \(l,r\) 的 LCS 长度。
如果 \(lcp + lcs < w\)，那么这两个点就没有贡献。
如果 \(lcp + lcs \ge w\)，那么这两个点就会有贡献，而且因为 \(lcs\) 和 \(lcp\) 可能有一部分重叠，所以我们可以继续平移这个 \(AA\) 串，最多可以平移重叠的长度位。
（画个图感性理解一下……）
这样的话就会在 \(a,b\) 上各有一个区间的贡献 \(+1\)，差分即可。
很多细节，还是那句话：画图！
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
using namespace std;
const int N = 3e4;
const int LG = 15;
int T,n;
int lg2[N + 5];
int a[N + 5],b[N + 5];
long long ans;
struct SuffixArray
{
int n,m;
char a[N + 5];
int sa[N + 5],rk[N * 2 + 5],tpr[N * 2 + 5],c[N + 5],height[N + 5];
int st[N + 5][LG + 5];
void build()
{
memset(sa,0,sizeof sa);
memset(rk,0,sizeof rk);
memset(tpr,0,sizeof tpr);
n = strlen(a + 1),m = 127;
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
++c[rk[i] = a[i]];
for(register int i = 1;i <= m;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
sa[c[rk[i]]--] = i;
for(register int w = 1,p = 0;p < n;w <<= 1,m = p)
{
p = 0;
for(register int i = 1;i <= w;++i)
tpr[++p] = n - w + i;
for(register int i = 1;i <= n;++i)
if(sa[i] > w)
tpr[++p] = sa[i] - w;
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
++c[rk[i]];
for(register int i = 1;i <= m;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
sa[c[rk[tpr[i]]]--] = tpr[i];
swap(rk,tpr),rk[sa[1]] = p = 1;
for(register int i = 2;i <= n;++i)
rk[sa[i]] = tpr[sa[i]] == tpr[sa[i - 1]] && tpr[sa[i] + w] == tpr[sa[i - 1] + w] ? p : ++p;
}
for(register int i = 1,k = 0;i <= n;++i)
{
k -= (bool)k;
for(;i + k <= n && sa[rk[i] - 1] + k <= n && a[i + k] == a[sa[rk[i] - 1] + k];++k);
height[rk[i]] = st[rk[i]][0] = k;
}
for(register int i = 1;i <= LG;++i)
for(register int j = 1;j + (1 << i) - 1 <= n;++j)
st[j][i] = min(st[j][i - 1],st[j + (1 << i - 1)][i - 1]);
}
int query(int l,int r)
{
l = rk[l],r = rk[r];
if(l > r)
swap(l,r);
++l;
int lg = lg2[r - l + 1];
return min(st[l][lg],st[r - (1 << lg) + 1][lg]);
}
} s,t;
int main()
{
for(register int i = 2;i <= N;++i)
lg2[i] = lg2[i / 2] + 1;
scanf("%d",&T);
while(T--)
{
scanf("%s",s.a + 1);
n = strlen(s.a + 1);
for(register int i = 1;i <= n;++i)
t.a[i] = s.a[n - i + 1];
s.build(),t.build();
memset(a,0,sizeof a),memset(b,0,sizeof b);
for(register int w = 1;w <= n / 2;++w)
for(register int i = w;i <= n;i += w)
{
int l = i,r = i + w;
int lcp = s.query(l,r),lcs = t.query(n - r + 2,n - l + 2);
lcp = min(lcp,w),lcs = min(lcs,w - 1);
if(lcp + lcs >= w)
++b[l - lcs],--b[l - w + lcp + 1],
++a[r + w - lcs - 1],--a[r + lcp];
}
for(register int i = 1;i <= n;++i)
a[i] += a[i - 1],b[i] += b[i - 1];
ans = 0;
for(register int i = 1;i < n;++i)
ans += a[i] * b[i + 1];
printf("%lld\n",ans);
}
}