首先看到k的范围就该知道这题不是倍增就是矩乘
首先肯定要求出任意一对串(a,b) a的后缀与b的前缀相同的最长长度是多少
考虑到kmp求出的失配指针是一个串最长后缀和前缀相等的长度
这里多个串我们只要用ac自动机即可
具体的，我们只要建立自动机，然后记录每个状态点是哪些串的子串
然后我们只要从每个串的结尾节点出发，顺着失配指针统计即可
然后我们把每个串看作一个点，点之间的边长度就是虽代表串的后缀前缀相同的最长长度
这个问题等价于求经过k条边的最短长度，倍增轻松搞定
1 const inf=2147483647*2147483647; 2 type node=record 3 po,next:longint; 4 end; 5 mtx=array[0..201,0..201] of int64; 6 7 var lcp:array[0..201,0..201] of longint; 8 d,p,w,fa,q:array[0..100010] of longint; 9 loc:array[0..201] of longint; 10 e:array[0..100010*200] of node; 11 trie:array[0..100010,'a'..'z'] of longint; 12 f,a:mtx; 13 ss:ansistring; 14 t,len,i,n,m,j,k:longint; 15 ans:int64; 16 17 function min(a,b:int64):int64; 18 begin 19 if a>b then exit(b) else exit(a); 20 end; 21 22 function max(a,b:longint):longint; 23 begin 24 if a>b then exit(a) else exit(b); 25 end; 26 27 procedure add(x,y:longint); 28 begin 29 inc(len); 30 e[len].po:=y; 31 e[len].next:=p[x]; 32 p[x]:=len; 33 end; 34 35 procedure ac; 36 var h,r,x,y,j:longint; 37 c:char; 38 begin 39 h:=1; 40 r:=0; 41 for c:='a' to 'z' do 42 if trie[0,c]>0 then 43 begin 44 inc(r); 45 q[r]:=trie[0,c]; 46 end; 47 48 while h<=r do 49 begin 50 x:=q[h]; 51 for c:='a' to 'z' do 52 if trie[x,c]>0 then 53 begin 54 y:=trie[x,c]; 55 inc(r); 56 q[r]:=y; 57 j:=fa[x]; 58 while (j>0) and (trie[j,c]=0) do j:=fa[j]; 59 fa[y]:=trie[j,c]; 60 end; 61 inc(h); 62 end; 63 end; 64 65 procedure get(k,x:longint); 66 var i,j:longint; 67 begin 68 while fa[x]<>0 do 69 begin 70 x:=fa[x]; 71 i:=p[x]; 72 while i<>0 do 73 begin 74 j:=e[i].po; 75 lcp[k,j]:=max(lcp[k,j],d[x]); 76 i:=e[i].next; 77 end; 78 end; 79 end; 80 81 procedure mul(var c:mtx; a,b:mtx); 82 var i,j,k:longint; 83 begin 84 for i:=1 to n do 85 for j:=1 to n do 86 c[i,j]:=inf; 87 88 for k:=1 to n do 89 for i:=1 to n do 90 for j:=1 to n do 91 c[i,j]:=min(c[i,j],a[i,k]+b[k,j]); 92 end; 93 94 begin 95 readln(n,m); 96 for i:=1 to n do 97 begin 98 readln(ss); 99 w[i]:=length(ss);100 j:=0;101 for k:=1 to w[i] do102 begin103 if trie[j,ss[k]]=0 then104 begin105 inc(t);106 trie[j,ss[k]]:=t;107 end;108 j:=trie[j,ss[k]];109 d[j]:=k;110 add(j,i);111 end;112 loc[i]:=j;113 end;114 ac;115 for i:=1 to n do116 get(i,loc[i]);117 for i:=1 to n do118 for j:=1 to n do119 a[i,j]:=w[j]-lcp[i,j];120 121 for i:=1 to n do122 for j:=1 to n do123 if i<>j then f[i,j]:=inf;124 dec(m);125 while m>0 do126 begin127 if m mod 2=1 then mul(f,f,a);128 m:=m shr 1;129 mul(a,a,a);130 end;131 ans:=inf;132 for i:=1 to n do133 for j:=1 to n do134 ans:=min(ans,f[i,j]+w[i]);135 writeln(ans);136 end.