P16780

· · 题解

并不那么经典的结论：n 个点的完全图有 n^{n-2} 个生成树。那么所有生成树有 (n-1)n^{n-2} 条边。

假设每条边被 x 课生成树包括，那么 \frac{n\times (n-1)\times x}{2}=(n-1)n^{n-2}，解得 x=2n^{n-3}。

那么答案为：

2n^{n-3}\times\sum_{i=1}^n\sum_{j=i+1}^n\operatorname{LCP}(S_i,S_j)

然后没了。字典树扫一遍就行了。

:::success[AC code]

const int N = 2e6 + 8;
const int p = 1e9 + 7;
int n;
ll ans = 0;
struct TRIE {
    int tot = 1;
    int cnt[N], son[N][28];
    int insert(string s) {
        int len = s.size();
        int now = 1, res = 0;
        rep(i, 0, len - 1) {
            int c = s[i] - 'a';
            if(!son[now][c]) son[now][c] = ++tot;
            now = son[now][c];
            res += cnt[now];
            cnt[now]++;
        }
        return res;
    }
}trie;
int qpow(ll x, int y) {
    ll res = 1;
    while(y) {
        if(y & 1) res = res * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return res;
}
int main()
{
  //  freopen("prefix.in", "r", stdin);
//    freopen("prefix.out", "w", stdout);
    read(n);
    rep(i, 1, n) {
        string s; read(s);
        ans += trie.insert(s);
    }
    ans %= p;
    if(n == 1) {
        puts("0");
        return 0;
    }
    if(n == 2) {
        print(ans);
        return 0;
    }
    print(2 * qpow(n, n - 3) % p * ans % p);
    return 0;
}

:::