中
等
的
字
符
串
中等的字符串
中等的字符串
正
解
部
分
\color{red}{正解部分}
正解部分
建出
A
c
Ac
Ac 自动机, 在自动机上
d
p
dp
dp,
设
F
[
i
,
j
]
F[i, j]
F[i,j] 表示
i
i
i 节点走
j
j
j 步所能得到的 最大值, 则
F
[
i
,
j
]
=
max
(
F
[
t
o
,
j
−
1
]
+
w
t
o
)
F[i, j] = \max(F[to, j-1] + w_{to})
F[i,j]=max(F[to,j−1]+wto), 时间复杂度
O
(
N
M
2
)
O(NM^2)
O(NM2) .
继续优化, 建立两个矩阵如下
[
F
1
,
0
F
2
,
0
,
F
3
,
0
.
.
.
F
t
o
t
,
0
]
\begin{bmatrix} F_{1,0} F_{2,0}, F_{3,0}\ ...\ F_{tot,0}\end{bmatrix}
[F1,0F2,0,F3,0 ... Ftot,0]
[
−
i
n
f
−
i
n
f
−
i
n
f
.
.
.
−
i
n
f
w
a
w
a
w
a
.
.
.
w
a
w
b
w
b
w
b
.
.
.
w
b
.
.
.
−
i
n
f
−
i
n
f
−
i
n
f
.
.
.
−
i
n
f
]
\begin{bmatrix} -inf -inf-inf\ ...\ -inf\\ w_{a}\ \ \ \ \ \ \ w_{a}\ \ \ \ \ w_{a}\ \ \ ...\ \ \ \ \ w_{a} \\w_{b}\ \ \ \ \ \ \ w_{b}\ \ \ \ \ w_{b}\ \ \ ...\ \ \ \ \ w_{b} \\ . \\ . \\ . \\ -inf -inf-inf\ ...\ -inf \end{bmatrix}
⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡−inf−inf−inf ... −infwa wa wa ... wawb wb wb ... wb...−inf−inf−inf ... −inf⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤
将两个矩阵相乘, 将加法替换为
max
\max
max 操作, 乘法替换为加法, 可以得到
[
F
1
,
1
=
max
(
F
1
,
0
−
i
n
f
,
F
1
,
0
+
w
1
,
.
.
.
,
F
1
,
0
+
w
t
o
t
)
,
.
.
.
F
t
o
t
,
1
]
[F_{1,1} = \max(F_{1,0}-inf, F_{1,0}+w_1,...,F_{1,0} + w_{tot}), ...F_{tot,1}]
[F1,1=max(F1,0−inf,F1,0+w1,...,F1,0+wtot),...Ftot,1] .
于是矩阵
2
2
2 的
N
N
N 次幂乘上 矩阵
1
1
1 即可得到答案矩阵 .
实
现
部
分
\color{red}{实现部分}
实现部分
注意 单位矩阵 为
[
0
−
i
n
f
.
.
.
−
i
n
f
−
i
n
f
0
.
.
.
−
i
n
f
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
−
i
n
f
−
i
n
f
.
.
.
0
]
\begin{bmatrix} 0 \ -inf\ ... \ -inf \\ -inf\ 0 \ ...\ -inf \\ ............... \\ -inf\ -inf\ ...\ 0\end{bmatrix}
⎣⎢⎢⎡0 −inf ... −inf−inf 0 ... −inf...............−inf −inf ... 0⎦⎥⎥⎤
#include<bits/stdc++.h>
#define reg register
#define fi first
#define se second
#define pb push_back
typedef long long ll
;
typedef std
::pair
<ll
, int> pr
;
const int maxn
= 100004;
const ll inf
= 0x3f3f3f3f3f3f3f3f;
int M
;
int A
[maxn
];
int dep
[maxn
];
int node_cnt
;
ll N
;
ll F
[20004][105];
bool vis
[maxn
];
char Smp
[205];
std
::vector
<int> Mp
[27];
struct Node
{ int nxt
, ch
[30], p
; } Trie_t
[maxn
];
void Add(char *s
, int x
){
int len
= strlen(s
), cur
= 0;
for(reg
int i
= 0; i
< len
; i
++){
int t
= s
[i
];
if(!Trie_t
[cur
].ch
[t
-'a']){
Trie_t
[cur
].ch
[t
-'a'] = ++ node_cnt
;
Mp
[t
-'a'].pb(node_cnt
);
dep
[node_cnt
] = dep
[cur
] + 1;
}
cur
= Trie_t
[cur
].ch
[t
-'a'];
}
Trie_t
[cur
].p
+= x
;
}
void Build_Ac(){
std
::queue
<int> Q
;
for(reg
int i
= 0; i
< 26; i
++) if(Trie_t
[0].ch
[i
]) Q
.push(Trie_t
[0].ch
[i
]);
while(!Q
.empty()){
int ft
= Q
.front(); Q
.pop();
Trie_t
[ft
].p
+= Trie_t
[Trie_t
[ft
].nxt
].p
;
for(reg
int i
= 0; i
< 26; i
++){
int &to
= Trie_t
[ft
].ch
[i
];
if(to
) Trie_t
[to
].nxt
= Trie_t
[Trie_t
[ft
].nxt
].ch
[i
], Q
.push(to
);
else to
= Trie_t
[Trie_t
[ft
].nxt
].ch
[i
];
}
}
}
struct Matrix
{
ll v
[205][205];
friend Matrix
operator * (const Matrix
&a
, const Matrix
&b
){
Matrix s
;
for(reg
int i
= 1; i
<= node_cnt
+1; i
++)
for(reg
int j
= 1; j
<= node_cnt
+1; j
++) s
.v
[i
][j
] = -inf
;
for(reg
int i
= 1; i
<= node_cnt
+1; i
++)
for(reg
int j
= 1; j
<= node_cnt
+1; j
++)
for(reg
int k
= 1; k
<= node_cnt
+ 1; k
++)
s
.v
[i
][j
] = std
::max(s
.v
[i
][j
], a
.v
[i
][k
]+b
.v
[k
][j
]);
return s
;
}
} P
, I
;
Matrix
Ksm(Matrix a
, ll b
){
Matrix s
;
for(reg
int i
= 1; i
<= node_cnt
+1; i
++)
for(reg
int j
= 1; j
<= node_cnt
+1; j
++) s
.v
[i
][j
] = (i
==j
)?0:-inf
;
while(b
){ if(b
& 1) s
= s
* a
; a
= a
* a
; b
>>= 1; }
return s
;
}
void Fuck(){
for(reg
int i
= 1; i
<= node_cnt
+1; i
++)
for(reg
int j
= 1; j
<= node_cnt
+1; j
++) P
.v
[i
][j
] = -inf
;
for(reg
int i
= 1; i
<= node_cnt
+1; i
++) P
.v
[1][i
] = 0;
I
.v
[1][1] = -inf
;
for(reg
int i
= 1; i
<= node_cnt
+1; i
++)
for(reg
int j
= 1; j
<= node_cnt
+1; j
++) I
.v
[i
][j
] = -inf
;
for(reg
int u
= 0; u
<= node_cnt
; u
++)
for(reg
int i
= 0; i
< 26; i
++)
I
.v
[Trie_t
[u
].ch
[i
]+1][u
+1] = Trie_t
[Trie_t
[u
].ch
[i
]].p
;
I
= Ksm(I
, N
); P
= P
* I
;
printf("%lld\n", P
.v
[1][1]);
}
int main(){
scanf("%lld%d", &N
, &M
);
for(reg
int i
= 1; i
<= M
; i
++) scanf("%d", &A
[i
]);
for(reg
int i
= 1; i
<= M
; i
++){ scanf("%s", Smp
); Add(Smp
, A
[i
]); }
Build_Ac(); Fuck();
return 0;
}
