题解：P16780 ⌈Xzy OI R1 T2⌋ 成成边

· · 题解

翻了一下题解区发现都是 Trie 树做法。模拟赛考了这题饭堂了没写 Trie 树。注意到原问题等价于所有二元组 (i,j) 的 \text{LCP}(s_i, s_j) 之和乘上一个完全图固定选择一条边之后的生成树数量。这个数量是 2\times n^{n-3}，赛时打表找出来的，其他题解有较详细证明，这里不多赘述。

考虑如何求所有二元组 (i,j) 的 \text{LCP}(s_i, s_j) 之和。我们将所有字符串按字典序排序，算出排序后的第 i 个字符串和第 i-1 个字符串的最长公共前缀记为 lcp_i。

接下来计算位于 i-1 之前的 j 和 i 的最长公共前缀长度。假设 i=6，我们得到了这样的 lcp 序列：

lcp  3 1 2 5 4
下标 2 3 4 5 i

这意味着，i 与 i-1 的前 4 位相同，i-1 与 i-2 的前 5 位相同，那么说明 i 与 i-2 的前 4 位相同。以此类推，我们可以得到：

LCP(1,i)=1
LCP(2,i)=1
LCP(3,i)=2
LCP(4,i)=4
LCP(5,i)=4

容易发现，由于我们对所有字符串排过序，i 与 j 的最长公共前缀长度为 j+1 到 i 的 lcp 的最小值（好像是一个经典结论来着）。这启发我们维护一个 lcp 的后缀最小值 mi 数组。当有新的 lcp 加入到末尾时，就往前遍历更新。如果 mi_j 已经小于 lcp_i，那么说明前面的都更小不需要更新，跳出循环即可。

因为对固定位置 j，更新时 mi_j 每次减小至少 1，初值 mi_j=lcp_j \le |s_j|，所以总的修改次数是 O(\sum |s_i|) 级别的。

我们在更新 mi 的同时维护 mi 数组的总和 sum，那么 sum 代表的就是 i 和前面所有 j 的最长公共前缀长度之和。把每次的 sum 累加最后乘以 2\times n^{n-3} 即可。

代码如下，可供参考：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,P=1e9+7;
int n,lcp[N],mi[N],sum,ans,fac=1;
struct Node{
    string s;
}a[N];
bool cmp(Node x,Node y){
    return x.s<y.s;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].s;
    for(int i=1;i<=n-3;i++)fac=1ll*fac*n%P;
    fac=2ll*fac%P;
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<=n;i++){
        int pos=0,len1=a[i-1].s.size(),len2=a[i].s.size();
        while(pos<len1&&pos<len2&&a[i-1].s[pos]==a[i].s[pos])pos++;
        lcp[i]=pos;sum=(sum+lcp[i])%P;mi[i]=lcp[i];
        for(int j=i-1;j>1;j--){
            if(mi[j]<=lcp[i])break;
            else{
                sum=(sum+P-mi[j])%P;
                mi[j]=lcp[i];
                sum=(sum+mi[j])%P;
            }
        }
        ans=(ans+sum)%P;
    }
    cout<<1ll*ans*fac%P;
    return 0;
}