【题解】渺茫的希望

· · 题解

一道题面十分具有欺骗性的题，至今为止已有数个验题人被这题的题面吓到以为是道字符串重工业题。

事实上直接构造即可，我们设 s_i 为字符 i 在字符串 S 中从左往右第一个出现的位置，将以这个位置开头的后缀称作 base_i 。那么 base_i 出现次数一定为 1 。我们随便找一个字符 i ，从 base_i 向所有不以 i 开头的子串连边。然后再找另一个字符 j ，从 base_j 向所有以 i 开头的除了 base_i 以外的子串连边。

设 S 一共有 p 个本质不同子串，我们来计算一下这样构造的代价：对于全部的 p-1 条边，其中一端固定为 base_i 或 base_j ，出现次数恒定为 1 ，另一端中除了 base_i 外每个本质不同子串都出现了一次，因此代价为 

(所有本质不同子串的出现次数之和-1)+(p-1)

考虑到所有本质不同子串出现次数之和即为 S 的子串个数 n(n+1)/2 ，因此答案为 n(n+1)/2+p-2 ，用后缀数组或者后缀自动机求出 p 即可。

最简单的，我们可以通过答案来证明这个解法的正确性。考虑在最小生成树中每个本质不同子串的度数至少为 1 ，因此每个本质不同子串的出现次数至少被计算一遍。中间的最长公共前缀的长度最短为 0 ，而总度数为 2(p-1)=2p-2 ，减去 p 个本质不同子串各出现一次的度数后，剩下 p-2 的度数对应的本质不同子串的出现次数至少为 1 。因此最小生成树的权值至少为 n(n+1)/2+p-2，与我们构造的答案相符，相当于我们通过构造证明了最小生成树的最小可能权值一定可以达到 。

发现还缺了些什么。上面的构造方案要求存在两个不同的字符 i 和 j 。要是 S 只有一种字符构成呢？事实上这种方案更好构造，最优方案即为将长度为 n 的子串与其它所有子串各连一条边。权值为 \sum_{i=1}^{n-1} 1+i+n-i+1 = (n+2)(n-1) 。特判一下即可。

尝试证明以上的结论。一共有 n 个本质不同子串，长度为 i 的子串出现次数为 n-i+1 。设一条边连接的两个本质不同子串长度为 x 和 y ，不妨设 x \le y 。那么这条边的权值为 (n-x+1)+(n-y+1)+x=2n-y+2 。如果要使这条边权值最小，那么就要使 y 最大，即让每个本质不同子串与长度为 n 的串连边。

标程代码使用 SAM 实现。

#include<bits/stdc++.h> 
#define N 200010
using namespace std;

int n;
long long ans;
char s[N];

struct SAM{
    int tr[N][30],fa[N],lst,tot,len[N];
    SAM() {lst=tot=1;}
    void insert(int c) {
        int p=lst,np=++tot;
        len[np]=len[p]+1,lst=np;
        while(p&&!tr[p][c]) tr[p][c]=np,p=fa[p];
        if(!p) {fa[np]=1;return ;}
        int q=tr[p][c];
        if(len[p]+1==len[q]) {fa[np]=q;return ;}
        int nq=++tot;
        len[nq]=len[p]+1;
        fa[nq]=fa[q],fa[q]=fa[np]=nq;
        memcpy(tr[nq],tr[q],sizeof(tr[q]));
        while(p&&tr[p][c]==q) tr[p][c]=nq,p=fa[p];
    }
    int buc[N],rk[N],in[N],dis[N];
    queue<int> q;
    int topo() {
        memset(dis,0,sizeof(dis));
        for(int i=1; i<=tot; i++) 
            for(int j=0; j<26; j++) if(tr[i][j]) in[tr[i][j]]++;
        q.push(1),dis[1]=1;
        while(!q.empty()) {
            int now=q.front();q.pop(),ans+=dis[now];
            for(int i=0; i<26; i++) if(tr[now][i]) {
                dis[tr[now][i]]+=dis[now];
                if(!(--in[tr[now][i]])) q.push(tr[now][i]);
            }
        }
    }
}sam;
int read() {
    int res=0,f=1;char ch=getchar();
    while(!isdigit(ch)) f=ch=='-'?-1:1,ch=getchar();
    while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
    return f*res;
}
int flag=1;
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=1; i<=n; i++) {
        sam.insert(s[i]-'a');
        if(s[i]!=s[1]) flag=0;
    }
    if(flag==1) {printf("%lld",1ll*(n+2)*(n-1));return 0;}
    sam.topo();
    printf("%lld",1ll*n*(n+1)/2+ans-3);
}