30%

枚举所有的分割情况通过字符串哈希判重即可

100%

本题的关键在于怎么分割字符串。

举个简单的例子。字典里共有4个串a,bcd,ab,cd。如何保证abcd对答案的贡献只被计算到一次？

构建两棵字典树 $tr_1$,$tr_2$。将所有单词正序插入 $tr_1$,倒序插入 $tr_2$。

在 $tr1$ 上dfs，访问到一个节点时，如果它的子结点中没有某个字母（设为c），那么就让答案加上以 c 开头的不同后缀的数量。

借用上面的例子进行说明：

访问到节点a，发现它有一个子结点b（字典内有单词ab），所以我们就只考虑不以b开头的后缀（以a和c开头的后缀），有三种，a,ab,cd，构成单词aa,aab,acd。

访问到节点ab，发现它没有子结点，那么以任何字母开头的后缀都满足条件，其中就包含cd，构成单词abcd。这样,abcd只会被分割为ab+cd并恰好计算一次。

这样忽视了一个问题：如果存在一个以c结尾的词，那么即使一个节点的子结点中包含c，也可以通过拼接得到这个前缀+c的结果。

比如：词典中有abc,dc，可以通过ab+c拼出abc这个词，但按照原来的算法无法找到。

所以我们记录每个字符串的尾字母。这个时候，如果一个词长度 $n\ge2$，那么它能够被自己的前 $n-1$ 个字符和最后一个字符连起来得到。但如果 $n=1$，这个词无法被构造出来，而它确实存在于新的词典中，所以需将ans加上1。全部代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4e5+5;
struct Trie{
    int n;
    int trie[N][26];
    LL cnt[26];
    Trie():n(0){}
    void insert(string s,bool rev){
        int u=0,len=s.length();
        if(!rev){
            for(int i=0;i<len;++i){
                int o=s[i]-'a';
                if(!trie[u][o]) trie[u][o]=++n;
                u=trie[u][o];
            }
        }
        else{
            for(int i=len-1;~i;--i){
                int o=s[i]-'a';
                if(!trie[u][o]) trie[u][o]=++n,++cnt[o];
                u=trie[u][o];
            }
        }
    }
} tr1,tr2;
LL ans;
int n;
bool ok[26],flag[26];
string s[N];
int main(){
    freopen("magic.in", "r", stdin);
    freopen("magic.out", "w", stdout);
    cin >> n;
    for(int i=1;i<=n;++i){
        cin>>s[i];
        tr1.insert(s[i],false);
        tr2.insert(s[i],true);
        int len=s[i].length();
        ok[s[i][len-1]-'a']=true;
        if(len==1 && !flag[s[i][0]-'a']){++ans;flag[s[i][0]-'a']=true;}
    }
    for(int u=1;u<=tr1.n;++u){
        for(int o=0;o<26;++o)
            if(!tr1.trie[u][o])
                ans+=tr2.cnt[o];
            else if(ok[o])
                ++ans;
    }
    cout << ans << "\n";
    return 0;
}

考察知识点

字典树 计数