#P10496. [2021年联测]字符串

    ID: 9613 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-Trie树上加权中位点增量维护势能分析LCA快速幂

[2021年联测]字符串

题目描述

有 nn 个非空的小写字母串 S1,…,SnS_1,\ldots,S_n。第 ii 个小写字母的权值为 xiyi+zix_i^{y_i}+z_i,字母按 a 到 z 的顺序编号。

允许对任意字符串执行以下操作,每次代价为所添加或删除字母的权值。

  • 在字符串末尾添加一个字母。
  • 删除非空字符串的最后一个字母。

对于每个 j=1,…,nj=1,\ldots,n,将前 jj 个字符串变成同一个字符串,目标字符串可以为空。求所需的最小总代价。先最小化实际总代价,再输出该最小值对 998244353998244353 取模的结果。

输入格式

第一行一个整数 nn。

第二、第三、第四行各有 2626 个整数,分别为 x1,…,x26x_1,\ldots,x_{26}、y1,…,y26y_1,\ldots,y_{26}、z1,…,z26z_1,\ldots,z_{26}。

接下来 nn 行,每行一个非空的小写字母串 SjS_j。

输出格式

输出 nn 行,第 jj 行一个整数,表示使前 jj 个字符串相同的最小总代价对 998244353998244353 取模后的结果。

原题的样例在下发文件中提供。

数据范围

1≤n≤1061\le n\le10^6,n≤∑i∣Si∣≤106n\le\sum_i |S_i|\le10^6。对每个字母,1≤xi,yi<9982443531\le x_i,y_i<998244353,0≤zi<9982443530\le z_i<998244353。

子任务 nn 上界 xi,yix_i,y_i 上界 字符集 ∑i∣Si∣\sum_i \lvert S_i\rvert 上界 特殊性质 分值 依赖
1 10 10 a,b,c 10 3
2 100 100 5 1
3 10310^3 10310^3 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 10310^3 10310^3 1–3、9
11 随机生成
12 15 1–11

性质 A:任取两个字符串,较短的是较长的前缀。等长时两串相同。

原 PDF 题面