记录编号	252373	评测结果	AAAAAAAAAA
题目名称	退票	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	1.871 s
提交时间	2016-04-20 10:48:59	内存使用	6.67 MiB

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 220
#define M 500010
using namespace std;
typedef long long ll;
//constant factor
ll INF=(1ll<<55);
ll hashmod=149;

int n,m,L[N]={0},R[N]={0};
ll f[N][N]={0},hash[M]={0},po[M]={0};
char s[M]={0};
int len=0;
ll MIN(ll a,ll b)
{
	if(a<b)return a;
	return b;
}
class MT
{
public:
	ll s[N][N];
	void full(ll c)
	{
		int i,j;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				s[i][j]=c;
			}
		}
	}
	MT()
	{
		full(0);
	}
	void print()
	{
		int i,j;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
		    {
				cout<<s[i][j]<<' ';
			}
			cout<<endl;
		}
	}
	MT operator *(MT b)
	{
		MT c;
		c.full(INF);
		int i,j,k;
		for(k=1;k<=n;k++)
		{
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=n;j++)
				{
					c.s[i][j]=MIN(c.s[i][j],s[i][k]+b.s[k][j]);
				}
			}
		}
		return c;
	}
}trans;
MT quickpow(MT a,ll k)
{
	MT c;
	c=a;
	k--;
	while(k)
	{
		if(k&1)c=c*a;
		a=a*a;
		k>>=1;
	}
	return c;
}
ll MTmin(MT a)
{
	ll sum=INF;
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			sum=MIN(sum,a.s[i][j]);
		}
	}
	return sum;
}
ll Hash(int l,int r)
{
	return hash[r]-hash[l-1]*po[r-l+1];
}
void read()
{
	scanf("%d%d",&n,&m);
	len=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+len+1);
		L[i]=len+1;
		R[i]=len=strlen(s+1);
		//cout<<L[i]<<' '<<R[i]<<endl;
	}
}
void init()
{
	int i,j,k,l;
	po[0]=1;
	for(i=1;i<=len;i++)hash[i]=hash[i-1]*hashmod+s[i],po[i]=po[i-1]*hashmod;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			l=min(R[i]-L[i]+1,R[j]-L[j]+1);
			if(i==j)l--;
			f[i][j]=R[j]-L[j]+1;
			//cout<<f[i][j]<<' '<<endl;
			for(k=l;k>=1;k--)
			{
				if(Hash(R[i]-k+1,R[i])==Hash(L[j],L[j]+k-1))
				{
					f[i][j]-=k;
					break;
				}
			}
		}
	}
}
MT temp;
void work()
{
	int i,j;
	MT ans;
	memcpy(trans.s,f,sizeof(trans.s));
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i==j)ans.s[i][j]=R[i]-L[i]+1;
			else ans.s[i][j]=INF;
		}
	}
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			cout<<f[i][j]<<' ';
		}
		cout<<endl;
	}
	trans.print();*/
	//ans.print();
	if(m>1)temp=quickpow(trans,m-1);
	ans=ans*temp;
	//temp.print();
	cout<<MTmin(ans)<<endl;
}
int main()
{
	freopen("ticketa.in", "r", stdin);
    freopen("ticketa.out", "w", stdout);
	read();
	init();
	work();
	return 0;
}