[poi2010]Hamsters

题意：Tz养了一群仓鼠，他们都有英文小写的名字，现在Tz想用一个字母序列来表示他们的名字，只要他们的名字是字母序列中的一个子串就算，出现多次可以重复计算。现在Tz想好了要出现多少个名字，请你求出最短的字母序列的长度是多少。(n <= 200,  m <= 1e9)

思路：首先可以处理出g[a][b]表示b接在a后面的长度(即重复部分之前都不算)

那么就可以转化成求长度m-1的最短路。

假设dis[i][a][b]为经过i步a走到b的最短路，那么dis[i][a][b] = min(dis[i/2][a][c] + dis[i-i/2][c][b]) (1<=c<=n)

那么是不是就可以利用快速幂的思想了。。

前面求g[a][b]可利用hash判断是否一样

code：

 /*
  * Author:  Yzcstc
  * Created Time:  2014/11/12 20:54:48
  * File Name: hamsters.cpp
  */
 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<cstdlib>
 #include<cmath>
 #include<algorithm>
 #include<string>
 #include<map>
 #include<set>
 #include<vector>
 #include<queue>
 #include<stack>
 #include<ctime>
 #define M0(x)  memset(x, 0, sizeof(x))
 #define repf(i, a, b) for (int i = (a); i <= (b); ++i)
 #define Inf  0x7fffffff
 #define M 10007
 using namespace std;
 typedef long long ll;
 const int maxn = ;
 int n, m;
 char str[];
 vector<int> hs[];
 int sz[maxn], pw[];
 ll A[maxn][maxn], B[maxn][maxn];
 ll s[maxn], tmp[maxn]; inline int Hash(const int &p, const int& l, const int& r){
        return hs[p][r] - hs[p][l-] * pw[r-l+];
 } void init(){
      int len, v;
      repf(i, , n){
            scanf("%s", str + );
            sz[i] = len = strlen(str + );
            hs[i].push_back(v = );
            repf(j, , len)
                 v = v * M + str[j], hs[i].push_back(v);
      }
 } void modify(ll *s, ll A[][maxn]){
      memset(tmp, 0x3f, sizeof(tmp));
 //     cout << tmp[0] << endl;
      for (int i = ; i <= n; ++i)
             for (int j = ; j <= n; ++j)
                    tmp[j] = min(tmp[j], s[i] + A[i][j]);
      repf(i, , n) s[i] = tmp[i];
 } void modify(ll A[][maxn]){
      memset(B, 0x3f, sizeof(B));
      repf(k, , n) repf(i, , n) repf(j, , n)
            B[i][j] = min(B[i][j], A[i][k] + A[k][j]);
      repf(i, , n) repf(j, , n) A[i][j] = B[i][j];
 } void quick(int n){
      for (;n>; n>>=){
            if (n & ) modify(s, A);
            modify(A);
      }
 } void solve(){
      repf(i, , n) repf(j, , n){
            A[i][j] = sz[j];
            for (int k = max(, sz[i]-sz[j]+); k <= sz[i]; ++k)
                 if (Hash(i, k, sz[i]) == Hash(j, , sz[i]-k+)){
                       A[i][j] = sz[j] - (sz[i]-k+);  break;
                 }
      }
      repf(i, , n) s[i] = sz[i];
      quick(--m);
      ll ans = 1LL<<;
 //     cout << ans << endl;
      repf(i, , n) ans = min(ans, s[i]);
      cout << ans << endl;
 }  int main(){
     pw[] = ;
     repf(i, , ) pw[i] = pw[i-] * M;
     while (scanf("%d%d", &n, &m) != EOF){
         init();
         solve();
     }
     return ;
 }