题面
Description
Tz养了一群仓鼠，他们都有英文小写的名字，现在Tz想用一个字母序列来表示他们的名字，只要他们的名字是字母序列中的一个子串就算，出现多次可以重复计算。现在Tz想好了要出现多少个名字，请你求出最短的字母序列的长度是多少。
Input
输入：第一行n（1<=n<=200）和m(1<=m<=10的9此方)，n表示有多少个仓鼠，m表示Tz希望出现名字的次数，接下来n行，每行都是仓鼠的名字（中间没有空格）。
Output
输出：一行，最短的字母序列的长度。
Sample Input
4 5
monika
tomek
szymon
bernard
Sample Output
23
Sample Output
23
题目大意
略.
题解
这一题的题面漏了一个条件: 字符串之间两两不相包含. 由于(n le 200), 不难想到让这些名字两两作一次KMP, 得到一个转移矩阵. 我们考虑如何让(m)个名字在所求的串中出现. 建立一个初始矩阵: 对角线为每个字符串的长度, 其余位置均为(+infty). 对初始矩阵与转移矩阵作(m - 1)次转移(使用倍增的方法, 类似于快速幂, 但不是矩阵乘法, 而是对应的行向量和列向量加起来取(min)值). 得到的矩阵中, (res_{i j})表示开始第一个名字为(i), 最后出现的名字为(j)的需要的最少字符数量.
在(res_{n imes n})中取min即可.
一些细节需要注意, 已经在代码中标注.
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 200, LEN = (int)1e5;
const long long INF = (long long)1e15;
namespace KMP
{
inline void initialize(char *str, int len, int *pre)
{
pre[0] = -1;
for(int i = 1; i < len; ++ i)
{
int p = pre[i - 1];
for(; ~ p && str[p + 1] ^ str[i]; p = pre[p]);
if(str[p + 1] == str[i])
++ p;
pre[i] = p;
}
}
inline int match(char *s, int len, char *t, int *pre)
{
int p = -1;
for(int i = 0; i < len; ++ i)
{
for(; ~ p && t[p + 1] ^ s[i]; p = pre[p]); // 假如s和t是同一个串的话, 则要特判
if(t[p + 1] == s[i] && (s != t || p + 1 < i))
++ p;
}
return p + 1;
}
}
struct matrix
{
long long a[N][N];
int n;
inline matrix(int _n)
{
n = _n;
}
inline matrix friend operator *(const matrix &A, const matrix &B)
{
static matrix res(A.n);
for(int i = 0; i < A.n; ++ i)
for(int j = 0; j < A.n; ++ j)
{
res.a[i][j] = INF;
for(int k = 0; k < A.n; ++ k)
res.a[i][j] = std::min(A.a[i][k] + B.a[k][j], res.a[i][j]);
}
return res;
}
};
inline void power(matrix A, int x, matrix &res)
{
for(; x; x >>= 1, A = A * A)
if(x & 1)
res = res * A;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("BZOJ2085.in", "r", stdin);
// freopen("BZOJ2085.out", "w", stdout);
#endif
int n, m;
scanf("%d%d", &n, &m);
static char str[N][LEN];
static int pre[N][LEN];
for(int i = 0; i < n; ++ i)
scanf("%s", str[i]), KMP::initialize(str[i], strlen(str[i]), pre[i]);
static matrix A(n);
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
A.a[i][j] = strlen(str[j]) - KMP::match(str[i], strlen(str[i]), str[j], pre[j]);
static matrix res(n);
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
res.a[i][j] = i ^ j ? INF : strlen(str[i]);
power(A, m - 1, res); // m要减1
long long ans = INF;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
ans = std::min(ans, res.a[i][j]);
printf("%lld", ans);
}