传送门

首先，可以把公式化成$\sum_{1 \leq i < j \leq N} i+j-2 \times \sum LCP(suf_i,suf_j)$,

先考虑前半段，可以化成$\sum_{i=1}^{n}i\times(n-i)+\sum_{j=2}^N j \times (j-1)$,再化简后就是$\frac{(N-1) \times N \times (N+1) }{2}$。

可以$O(1)$求。接着考虑后半段。

因为后缀自动机的Parent树是逆序后缀树，所以逆序字符串建SAM搞出后缀树。在后缀树上搞事情。

在后缀树上，两个串的LCP就是他们LCA的深度，考虑用排列组合。

设$fv$为父亲边的边权，可以得到$f[i]=fv \times C_{size}^{2}$。

因为我们考虑的实际上还是每条边对答案的贡献。

//BZOJ 3238//by Cydiater//2017.1.21#include <iostream>#include <iomanip>#include <ctime>#include <cmath>#include <cstring>#include <string>#include <queue>#include <map>#include <cstdlib>#include <cstdio>#include <algorithm>#include <bitset>#include <set>#include <vector>using namespace std;#define ll long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)const int MAXN=1e6+5;const int oo=0x3f3f3f3f;ll ans=0,N;char s[MAXN];struct Graph{	int LINK[MAXN],len;	ll siz[MAXN];	struct edge{		int y,next,v;	}e[MAXN<<1];	inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}	inline void Insert(int x,int y,int v){insert(x,y,v);insert(y,x,v);}	void TreeDP(int node,int fa,ll dist){		Auto(i,node)if(e[i].y!=fa){			TreeDP(e[i].y,node,e[i].v);			siz[node]+=siz[e[i].y];		}		ans-=dist*(siz[node]*(siz[node]-1));	}}G;struct SAM{	int son[MAXN][26],pre[MAXN],step[MAXN],now,cnt;	SAM(){now=cnt=1;}	void Extend(int nxt){		int p=now,np=++cnt;now=np;		step[np]=step[p]+1;G.siz[np]=1;		for(;p&&!son[p][nxt];p=pre[p])son[p][nxt]=np;		if(!p)pre[np]=1;		else{			int q=son[p][nxt],nq;			if(step[q]==step[p]+1)pre[np]=q;			else{				step[(nq=++cnt)]=step[p]+1;				memcpy(son[nq],son[q],sizeof(son[q]));				pre[nq]=pre[q];				pre[np]=pre[q]=nq;				for(;son[p][nxt]==q;p=pre[p])son[p][nxt]=nq;			}		}	}	void GraphBuilder(){		up(i,2,cnt)G.Insert(pre[i],i,step[i]-step[pre[i]]);	}}sam;namespace solution{	void Prepare(){		scanf("%s",s+1);		N=strlen(s+1);		down(i,N,1)sam.Extend(s[i]-‘a‘);		sam.GraphBuilder();	}	void Solve(){		ans=(N+1)*(N)*(N-1)>>1;		G.TreeDP(1,0,0);		cout<<ans<<endl;	}}int main(){	freopen("input.in","r",stdin);	using namespace solution;	Prepare();	Solve();	return 0;}

BZOJ3238: [Ahoi2013]差异