CodeForces - 696D
题解
如果一个串s1包含于另一个串s2，那么val[s2] += val[s1]。即统计每个串所包含的所有字串和本身的值的和。
初始化矩阵，结点s1连向另外一个结点s2，权值为s2的值。表示s1可以一步到达s2。最后L个矩阵相乘，表示一个结点可以经过L步到达另一个结点。我们要找root结点经过L步可以到达的权值最大的结点。
注意矩阵相乘和之前的不一样，因为我们要统计结点i经过L步到j的最大权值，所以c[i][j] = max(c[i][j],a[i][k] + b[k][j])，类似floyd算法。如果走不通，则初始化为-1。
进行矩阵快速幂时，ans不能初始化为单位矩阵，因为这不是一般的矩阵乘法，我们就在base基础上运算。
最后有一个坑：传递矩阵为参数时，不能按值，要按引用，否则程序崩溃。。。orz
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int const N = 200 + 10;
int tot;
ll val[N];
struct Node{
Node *next[26];
Node *fail;
ll cnt; //判断是否是结尾，即危险结点
int index; //结点的标号
Node(){
for(int i=0;i<26;i++) next[i] = NULL;
fail = NULL;
cnt = 0;
index = tot++;
}
}*q[500010],*root,*trie[N];
void Insert(char *s,int val){
int len = strlen(s);
Node *now = root;
for(int i=0;i<len;i++){
int to = s[i] - 'a';
if(now->next[to] == NULL){
now->next[to] = new Node();
trie[tot-1] = now->next[to];
}
now = now->next[to];
}
now->cnt += val;
}
void Get_Fail(){
int head = 0,tail = 0;
q[head++] = root;
root->fail = NULL;
while(head != tail){
Node *tmp = q[tail++];
Node *p;
for(int i=0;i<26;i++){
if(tmp->next[i] == NULL){ //空指针
if(tmp == root)
tmp->next[i] = root;
else
tmp->next[i] = tmp->fail->next[i];
continue;
}
if(tmp == root) tmp->next[i]->fail = root;
else{
p = tmp->fail;
if(p == NULL) continue;
if(p->next[i]){
tmp->next[i]->fail = p->next[i];
tmp->next[i]->cnt += p->next[i]->cnt; //把出现的所有前缀的值都累加起来
}
}
q[head++] = tmp->next[i];
}
}
}
struct mat{
ll m[N][N];
mat(){memset(m,-1,sizeof(m));}
inline friend mat operator * (const mat& a,const mat& b){
mat c;
for(int i=0;i<tot;i++)
for(int j=0;j<tot;j++)
for(int k=0;k<tot;k++)
if(a.m[i][k] != -1 && b.m[k][j] != -1)
c.m[i][j] = max(c.m[i][j],a.m[i][k] + b.m[k][j]);
return c;
}
};
mat quick(mat& base,ll l){ //按引用传送
mat ans = base;
l--;
while(l){
if(l & 1) ans = base * ans;
base = base * base;
l >>= 1;
}
return ans;
}
int main(){
int n;
ll m;
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
root = new Node();
trie[tot-1] = root;
for(int i=1;i<=n;i++){
char str[N];
scanf(" %s",str);
Insert(str,val[i]);
}
Get_Fail();
mat base,ans;
for(int i=0;i<tot;i++){
for(int j=0;j<26;j++){
base.m[i][trie[i]->next[j]->index] = trie[i]->next[j]->cnt;
}
}
ans = quick(base,m);
ll res = 0;
for(int i=0;i<tot;i++)
res = max(res,ans.m[0][i]);
printf("%lld\n",res);
return 0;
}
