题意：求\(\sum_{1<=i<j<=n} len(T_i) + len(T_j) - 2*LCP(T_i,T_j)\)
思路：首先考虑把式子化简一下：
原式
= \(\sum_{1<=i<j<=n} len(T_i) + len(T_j) - 2 * \sum_{1<=i<j<=n}LCP(T_i,T_j)\)
= $\sum_{1<=i<j<=n} (n - i + 1) + (n - j + 1) - 2 * \sum_{1<=i<j<=n}LCP(T_i,T_j) $
= \(((n + 1) * n * (n - 1) / 2) - 2 * \sum_{1<=i<j<=n}LCP(T_i,T_j)\)
前面\(O(1)\)算一下，关键是后面求最长公共前缀，\(SAM\)跑一下即可，或者后缀树\(dp\)（懒得写了）。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 500005;
char s[maxn];
int cnt = 1;
int lst = 1;
int rt = 1;
int son[maxn << 1][26];
int fa[maxn << 1];
int dis[maxn << 1];
int siz[maxn << 1];
int _cnt;
struct edge {
int to;
int nxt;
}e[maxn << 2];
ll ans;
int head[maxn<<2];
inline void extend(int c) {
int p = lst;
int np = ++cnt;
lst = np;
siz[np] = 1;
while(p && !son[p][c]) son[p][c] = np,p = fa[p];
if(!p) {
fa[np] = rt;
}
else {
int q = son[p][c];
if(dis[q] == dis[p] + 1) fa[np] = q;
else {
int nq = ++cnt;
memcpy(son[nq],son[q],sizeof(son[nq]));
fa[nq] = fa[q];
dis[nq] = dis[p] + 1;
fa[np] = fa[q] = nq;
while(son[p][c] == q) {
son[p][c] = nq;
p = fa[p];
}
}
}
}
inline void Add_edge(int u,int v) {
e[++_cnt].to = v;
e[_cnt].nxt = head[u];
head[u] = _cnt;return;
}
inline void dfs(int x) {
for(int i = head[x];i;i=e[i].nxt) {
int y = e[i].to;
dfs(y);
ans += (ll)siz[x] * siz[y] * dis[x];
siz[x] += siz[y];
}
}
int main () {
scanf("%s",s + 1);
int len = strlen(s + 1);
for(int i = len;i >= 1; --i) {
extend(s[i] - 'a');
}
for(int i = 2;i <= cnt; ++i) {
Add_edge(fa[i],i);
}
dfs(1);
printf("%lld\n",(ll)(len - 1) * len * (len + 1) / 2 - ans * 2);
return 0;
}