题面

给出 $n$个互不包含的字符串，要求你求出一个最短的字符串 $S$，使得这 $n$ 个字符串在 $S$ 中总共至少出现$m$次，问 $S$ 最短是多少。

思路

把题目转化一下，求出$F[i][j]$表示把$S[j]$接在$S[i]$后面的代价，这个用$substr$比较或者$hash$都可以，然后我们得到了一个矩阵$F$。设一个矩阵$A$，大小为$[n]$，$A[i]$表示为出现了$x$个字符串并且以$S[i]$结尾的最小长度，$x$即为变换次数。考虑单次变换$A[1-n]$会与$F[1-n][i]$变化加法取$min$即为在每个现有以$S[1-n]$结尾的字符串后添加$S[i]$的最小长度，也就是A*F=A’，$A'[i]=min(A[k]+F[k][i],A'[i])$这也就是$floyd$，简单矩阵快速幂即可。

注意点

$darkbzoj$的题面莫得说互不包含，害我思考了好久包含怎么办（如果包含则一次变换不一定使得出现次数只加$1$，可能加更多）

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
string s[205];
LL n,m,b[205][205],a[2][205],Min=99999999999999,res[205][205];
inline void read(LL &x)
{
    LL f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline void mul(LL a[205][205],LL b[205][205],LL c[205][205])
{
	LL tmp[205][205];
	for (LL i=1;i<=n;i++) for (LL j=1;j<=n;j++) tmp[i][j]=99999999999999;
	for (LL i=1;i<=n;i++)
	{
		for (LL j=1;j<=n;j++)
		{
			for (LL k=1;k<=n;k++)
			tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]);
		}
	}
	for (LL i=1;i<=n;i++) for (LL j=1;j<=n;j++) c[i][j]=tmp[i][j];
}
inline void mull(LL a[2][205],LL b[205][205],LL c[2][205])
{
	LL tmp[2][205];
	for (LL i=1;i<=1;i++) for (LL j=1;j<=n;j++) tmp[i][j]=99999999999999;
	for (LL i=1;i<=1;i++)
	{
		for (LL j=1;j<=n;j++)
		{
			for (LL k=1;k<=n;k++)
			tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]);
		}
	}
	for (LL i=1;i<=1;i++) for (LL j=1;j<=n;j++) c[i][j]=tmp[i][j];
}
inline LL calc(LL x,LL y)
{
    LL lenx=s[x].size()-1,leny=s[y].size()-1;
    if (x!=y) {for (LL i=min(lenx,leny)+1;i>=1;i--) if (s[x].substr(lenx-i+1,i)==s[y].substr(0,i)) return i;}
    else for (LL i=min(lenx,leny);i>=1;i--) if (s[x].substr(lenx-i+1,i)==s[y].substr(0,i)) return i;
	return 0;
}
inline void ksm(LL base[205][205],LL index)
{
	
	for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)res[i][j]=base[i][j];
	while (index)
	{
		if (index&1) mul(res,base,res);
		mul(base,base,base);
		index>>=1;
	}
}
int main()
{ 
    read(n),read(m);
    for (LL i=1;i<=n;i++) cin>>s[i];
    for (LL i=1;i<=n;i++)  for (LL j=1;j<=n;j++)  b[i][j]=s[j].size()-calc(i,j);
//    for (LL i=1;i<=n;i++)
//    {
//    	for (LL j=1;j<=n;j++) cout<<b[i][j]<<" ";
//    	cout<<endl;
//	}
    for (LL i=1;i<=n;i++)	a[1][i]=s[i].size();
    m--;
    if (m==0) {for (LL i=1;i<=n;i++) Min=min(Min,a[1][i]);cout<<Min<<endl;return 0;}
    ksm(b,m-1);
    mull(a,res,a);
    for (LL i=1;i<=n;i++) Min=min(Min,a[1][i]);cout<<Min<<endl;return 0;
	return 0;
}