题解：P12238 [蓝桥杯 2023 国 Java A] 单词分类

· · 题解

\color{blue}{\texttt{[Analysis]}}

既然都是字符串前缀的问题了，那当然首先就应该想到 Trie 树。

我们可以发现这么一个性质，如果选从根到 Trie 树上某一点形成给定字符串作为前缀，那么子树内所有的字符串都会被归为这个类，子树外的其它字符串都不会被归为这个类。

于是可以想到在 Trie 上进行 dp。用 f_{u,k} 表示把子树 u 内的字符串分为 k 类的方案数。

根据上面的性质，其实这个 dp 等价于从 u 及其子树中选出 k 个点的方案数，因而转移方程显然。

但是需要注意的是，如果选择了 u 这个点，那么 u 的子树的点都不可以被选取，不然就会有些字符串被分入两个组中。当然，如果 k=1，那么选择 u 也是可能的合法的选择。

另外，因为每个字符串都要被分入其中一个组，因此 k 不能小于等于 0。

考虑清楚边界情况就可以开始写代码了。

注意有一种比较特别的情况：如果 Trie 树上一个非叶子节点 u 也对应着某个字符串。此时字典存在某个字符串为另外一个字符串的前缀。这时 u 的子树只能分为 1 类，即以节点 u 对应的字符串作为前缀分类。不然，要么节点 u 对应的字符串无法被归为任何一类，要么 u 的子树内的某个字符串被分入两类。

另外，由于每个节点最多也就 3 个子树，因此没必要写得那么复杂，枚举每棵子树内选取多少个点就可以了。

时间复杂度最多 O(NK^2 \times \max \{ |s| \})。其中 \max \{ |s| \} 表示字符串长度的最大值，实际上远远达不到这个上界。

\color{blue}{\text{Code}} 
const int mod=1e9+7;
const int N=210,M=110,L=2010;

int id(char ch){
    switch (ch){
        case 'l': return 0;
        case 'q': return 1;
        case 'b': return 2;
        default: return -1;
    }
}

struct Trie_Tree{
    int ch[L][3],ndcnt,cnt[L],child[L];
    bool flag[L];

    void init(){
        memset(ch,-1,sizeof(ch));
        memset(cnt,0,sizeof(cnt));
        memset(flag,false,sizeof(flag)); 
        memset(child,0,sizeof(child));
        ndcnt=0;
    }

    void insert(string s){
        int l=s.length(),u=0;

        for(int i=0;i<l;i++){
            int c=id(s[i]);

            if (ch[u][c]==-1){
                ch[u][c]=++ndcnt;
                ++child[u]; 
            }

            ++cnt[u];//统计字符串的数量 
            u=ch[u][c];
        }
        ++cnt[u];
        flag[u]=true;
    }
}trie;

int f[L][M],n,m;

int dp(int u,int k){ 
    if (trie.cnt[u]<k) return 0;
    if (~f[u][k]) return f[u][k];
    if (k<=0) return 0; 
    if (trie.flag[u]) return k==1;

    int res=((k==1)?1:0);

    if (trie.child[u]==1){
        int c;
        if (~trie.ch[u][0]) c=trie.ch[u][0];
        else if (~trie.ch[u][1]) c=trie.ch[u][1];
        else c=trie.ch[u][2];

        res=(res+dp(c,k))%mod;
    }
    else if (trie.child[u]==2){
        int c1,c2;
        if (~trie.ch[u][0]){
            c1=trie.ch[u][0];
            if (~trie.ch[u][1]) c2=trie.ch[u][1];
            else c2=trie.ch[u][2];
        }
        else c1=trie.ch[u][1],c2=trie.ch[u][2];

        for(int i=1;i<k;i++)
            res=(res+1ll*dp(c1,i)*dp(c2,k-i)%mod)%mod;
    }
    else{
        for(int i=1;i<k;i++)
            for(int j=1;j<k-i;j++)
                res=(res+1ll*dp(trie.ch[u][0],i)*dp(trie.ch[u][1],j)%mod*dp(trie.ch[u][2],k-i-j)%mod)%mod;
    }

    return f[u][k]=res;
}

int main(){
    cin>>n>>m;
    trie.init();
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        trie.insert(s);
    }

    memset(f,-1,sizeof(f));

    printf("%d",dp(0,m));

    return 0;
}