现在有 \(n\) 个字符串，每个字符串有个价值，要求写一个长度为 \(m\) 的字符串，其价值为所含子串的价值和。\(1\leq n\leq 200,1\leq m\leq 10^14\)。
如果 AC 自动机 \(j\) 的位置能跳到 \(k\)，那 \(dp[i][j]\) 就可以转移到 \(dp[i+1][k]\)。
\[dp[i][j]+val[k]\to dp[i+1][k]\,(j\to k)
\]
重新定义矩阵乘法为 \(C=A\cdot B\Leftrightarrow C_{i,j}=\max\{A_{i,k}+B_{k,j}\}\)
答案矩阵的 \((1,k)\) 由原矩阵的 \((1,j)\) 转移而来，为原矩阵的第 \(1\) 行与转移矩阵第 \(k\) 列相乘的结果。因此转移矩阵 \((j,k)\) 为 \(val[k]\)。
要用 \(-\inf\) 去约束可不可以走到的位置。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=210,M=27;
int n,m,a[N],tot=1,ch[N][M],fail[N],cnt[N],c[N][N],f[N][N],res[N][N],ans;
char s[N];
void insert(char* s,int id){
int len=strlen(s+1),p=1;
for(int i=1;i<=len;i++){
int k=s[i]-‘a‘;
if(!ch[p][k]) ch[p][k]=++tot;
p=ch[p][k];
}
cnt[p]+=a[id];
}
void getfail(){
queue<int>q;
for(int i=0;i<26;i++) ch[0][i]=1;
q.push(1),fail[1]=0;
while(q.size()){
int x=q.front();q.pop();
cnt[x]+=cnt[fail[x]]; //!
for(int i=0;i<26;i++){
int k=ch[x][i];
if(k) fail[k]=ch[fail[x]][i],q.push(k);
else ch[x][i]=ch[fail[x]][i];
}
}
}
void mul(int a[N][N],int b[N][N]){
memset(c,-0x3f,sizeof(c));
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++)
for(int k=1;k<=tot;k++)
c[i][j]=max(c[i][j],a[i][k]+b[k][j]); //!
memcpy(a,c,sizeof(c));
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
scanf("%s",s+1),insert(s,i);
getfail();
memset(f,-0x3f,sizeof(f));
for(int i=1;i<=tot;i++)
for(int j=0;j<=26;j++)
f[i][ch[i][j]]=cnt[ch[i][j]];
memset(res,-0x3f,sizeof(res)),res[1][1]=0; //!
for(;m;m>>=1,mul(f,f))
if(m&1) mul(res,f);
for(int i=1;i<=tot;i++) ans=max(ans,res[1][i]);
printf("%lld\n",ans);
return 0;
}