设g[i][j]为i串至少加上几个字符后才能包含j，可以通过Hash求出。

然后就是求经过m-1条边的最短路，用倍增加速Floyed即可，时间复杂度$O(n^3\log m)$。

 

#include
     
      #include
      
       #define rep(i,n) for(int i=0;i
       
        b)a=b;}struct mat{  ll a[N][N];  mat(){}  inline mat operator*(mat b){    mat c;    rep(i,n)rep(j,n)c.a[i][j]=inf;    rep(k,n)rep(i,n)rep(j,n)up(c.a[i][j],a[i][k]+b.a[k][j]);    return c;  }}G,B;int main(){  scanf("%d%d",&n,&m);  rep(i,n){    scanf("%s",s);    st[i]=t,len[i]=std::strlen(s);    rep(j,len[i])a[t+j]=s[j];    en[i]=t+len[i]-1,t+=len[i];  }  for(pow[0]=i=1;i
        
         >=1,G=G*G)if(m&1){if(!flag)B=G,flag=1;else B=B*G;}  rep(i,n)rep(j,n)up(ans,B.a[i][j]+len[i]);  return printf("%lld",ans),0;}