记录编号	252527	评测结果	AAAAAAAAAA
题目名称	退票	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.915 s
提交时间	2016-04-20 16:29:19	内存使用	2.60 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEL=100010,SIZEN=210,MOD=1000007;
typedef long long LL;
const LL hash_mul=149ll,INF=1e12;
int N,M;
LL hash[SIZEL]={0};
LL pos[SIZEL]={0};
int in[SIZEN],out[SIZEN];
char str[SIZEL];
int len;
void read()
{
	scanf("%d%d",&N,&M);
	out[0]=-1;
	for(int i=1;i<=N;i++)
	{
		in[i]=out[i-1]+1;
		scanf("%s",str+in[i]);
		out[i]=strlen(str)-1;
	}
	len=out[N]+1;
	pos[0]=1;
	hash[0]=str[0];
	for(int i=1;i<len;i++)
	{
		hash[i]=hash[i-1]*hash_mul+str[i];
		pos[i]=pos[i-1]*hash_mul;
	}
}
LL f[SIZEN][SIZEN];
LL HASH(int l,int r)
{
	//for(int i=l;i<=r;i++) cout<<str[i];
	//cout<<" "<<hash[r]-hash[l-1]*pos[r-l+1]<<" ";
	return hash[r]-hash[l-1]*pos[r-l+1];
}
class miku
{
public:
	int n,m;
	LL s[201][201];
	LL mi()
	{
		LL ans=INF;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++) ans=min(ans,s[i][j]);
		}
		return ans;
	}
	void print()
	{
		cout<<n<<" "<<m<<endl;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++) cout<<s[i][j]<<" ";
			cout<<endl;
		}
	}
}D,A;
miku operator *(miku a,miku b)
{
	miku c;
	c.n=a.n;c.m=b.m;
	for(int i=1;i<=c.n;i++)
	{
		for(int j=1;j<=c.m;j++)
		{
			c.s[i][j]=INF;
			for(int k=1;k<=a.m;k++) c.s[i][j]=min(c.s[i][j],a.s[i][k]+b.s[k][j]);
		}
	}
	return c;
}
miku quickpow(miku x,int t)
{
	miku re;
	bool fg=0;
	while(t)
	{
		if(t&1)
		{
			if(fg) re=re*x;
			else re=x,fg=1;
		}
		t>>=1;x=x*x;
	}
	return re;
}
void work()
{
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			int l=min(out[j]-in[j]+1,out[i]-in[i]+1);
			if(i==j) l--;
			f[i][j]=out[j]-in[j]+1;
			for(int k=l;k>0;k--)
			{
				//cout<<HASH(out[i]-k+1,out[i])<<" "<<HASH(in[j],in[j]+k-1)<<endl;
				if(HASH(out[i]-k+1,out[i])==HASH(in[j],in[j]+k-1))
				{
					f[i][j]-=k;
					break;
				}
				//cout<<endl;
			}
		}
	}
	D.n=D.m=N;
	A.n=A.m=N;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++) D.s[i][j]=f[i][j];
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++) 
		{
			if(i==j) A.s[i][j]=out[i]-in[i]+1;
			else A.s[i][j]=INF;
		}
	}
	if(M>1) D=quickpow(D,M-1);
	A=A*D;
	//A.print();
	printf("%lld\n",A.mi());
}
int main()
{
	freopen("ticketa.in","r",stdin);
	freopen("ticketa.out","w",stdout);
	read();
	work();
	return 0;
}