题目描述
有 n 个非空的小写字母串 S1,…,Sn。第 i 个小写字母的权值为 xiyi+zi,字母按 a 到 z 的顺序编号。
允许对任意字符串执行以下操作,每次代价为所添加或删除字母的权值。
- 在字符串末尾添加一个字母。
- 删除非空字符串的最后一个字母。
对于每个 j=1,…,n,将前 j 个字符串变成同一个字符串,目标字符串可以为空。求所需的最小总代价。先最小化实际总代价,再输出该最小值对 998244353 取模的结果。
输入格式
第一行一个整数 n。
第二、第三、第四行各有 26 个整数,分别为 x1,…,x26、y1,…,y26、z1,…,z26。
接下来 n 行,每行一个非空的小写字母串 Sj。
输出格式
输出 n 行,第 j 行一个整数,表示使前 j 个字符串相同的最小总代价对 998244353 取模后的结果。
原题的样例在下发文件中提供。
数据范围
1≤n≤106,n≤∑i∣Si∣≤106。对每个字母,1≤xi,yi<998244353,0≤zi<998244353。
| 子任务 |
n 上界 |
xi,yi 上界 |
字符集 |
∑i∣Si∣ 上界 |
特殊性质 |
分值 |
依赖 |
| 1 |
10 |
10 |
a,b,c |
10 |
|
3 |
|
| 2 |
100 |
|
100 |
5 |
1 |
| 3 |
103 |
103 |
7 |
1、2 |
| 4 |
|
|
15 |
1–3 |
| 5 |
|
a |
A |
5 |
|
| 6 |
|
10 |
5 |
| 7 |
2 |
|
5 |
|
| 8 |
3 |
7 |
| 9 |
100 |
100 |
10 |
1、2 |
| 10 |
103 |
103 |
1–3、9 |
| 11 |
|
|
随机生成 |
|
| 12 |
|
15 |
1–11 |
性质 A:任取两个字符串,较短的是较长的前缀。等长时两串相同。
原 PDF 题面