$\text{[Problem?Discription]}$

Copy from luogu.

$\text{[Analysis]}$

既然都是字符串前綴的問題了，那當然首先就應該想到 $\text{Trie}$ 樹。

我們可以發現這么一個性質，如果選從根到 $\text{Trie}$ 樹上某一點形成給定字符串作為前綴，那么子樹內所有的字符串都會被歸為這個類，子樹外的其它字符串都不會被歸為這個類。

于是可以想到在 $\text{Trie}$ 上進行 $\text{dp}$。用 $f_{u,k}$ 表示把子樹 $u$ 內的字符串分為 $k$ 類的方案數。

根據上面的性質，其實這個 $\text{dp}$ 等價于從 $u$ 及其子樹中選出 $k$ 個點的方案數，因而轉移方程顯然。

但是需要注意的是，如果選擇了 $u$ 這個點，那么 $u$ 的子樹的點都不可以被選取，不然就會有些字符串被分入兩個組中。當然，如果 $k=1$，那么選擇 $u$ 也是可能的合法的選擇。

另外，因為每個字符串都要被分入其中一個組，因此 $k$ 不能小于等于 $0$。

考慮清楚邊界情況就可以開始寫代碼了。

另外，由于每個節點最多也就 $3$ 個子樹，因此沒必要寫得那么復雜，枚舉每棵子樹內選取多少個點就可以了。

時間復雜度最多 O ( N K × max ? { ∣ s ∣ } ) O(NK \times \max \{ |s| \}) O(NK×max{∣s∣})。其中 max ? { ∣ s ∣ } \max \{ |s| \} max{∣s∣} 表示字符串長度的最大值。

$\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;
}