#P12483. [2025年福建省队集训]回文

    ID: 11646 传统题 5000ms 888MiB 尝试: 8 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS贡献法根号分治ManacherTrie子树转区间扫描线懒标记线段树后缀数组Kasai 算法LCP+RMQST 表单调栈

[2025年福建省队集训]回文

问题描述

给定大小为 nn 的字符串序列 SS 和大小为 mm 的字符串序列 TT,其中 SS 的第 ii 个字符串为 SiS_i,TT 的第 jj 个字符串为 TjT_j。

定义一个字符串的权值 f(s)f(s) 为 ss 中最长奇回文子串的半径长度。例如 aba 的半径长度为 22,ababa 的半径长度为 33。

定义两个字符串的加法 s+ts + t 为把两个字符串拼接起来得到的新字符串。

求:

∑i=1n∑j=1mf(Si+Tj)\sum_{i=1}^{n} \sum_{j=1}^{m} f(S_i + T_j)

输入输出格式

输入格式

第一行输入两个正整数 n,mn, m。

接下来 nn 行,输入 nn 个字符串 SiS_i。

再接下来 mm 行,输入 mm 个字符串 TjT_j。

输出格式

输出一行,表示上述求和式的值。

样例

输入 #1

3 3
a
aba
aaba
b
ba
ab

输出 #1

19

其余三个样例见下发文件。

样例解释

回文半径长度 T1T_1 T2T_2 T3T_3
S1S_1 1 2 1
S2S_2 2 3 2
S3S_3 3

数据范围

令 s=max⁡(∑∣Si∣,∑∣Ti∣)s = \max(\sum |S_i|, \sum |T_i|)。

本题共有 4 个子任务,只有通过子任务中所有数据才能获得所有分数。

子任务编号 分数 特殊条件
1 20 s≤5000s \leq 5000
2 30 n=1n = 1
3 20 保证所有字符在 {a,b}\{a, b\} 中随机
4 30 依赖子任务 1, 2, 3

对于 100% 的数据,满足 1≤n,m,s≤4×1051 \leq n, m, s \leq 4 \times 10^5,保证输入的字符串只包含小写字母。