#P17278. [2024年南开中学集训]Heavensdoor

    ID: 16393 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500AC自动机动态规划字符串算法基础模拟

[2024年南开中学集训]Heavensdoor

题目描述

给定 nn 个字符串 s1,s2,⋯ ,sns_1,s_2,\cdots,s_n。

设 M(s,t)M(s,t) 表示 ss 中等于 tt 的连续子串的个数,s+ts+t 表示 s,ts,t 拼接在一起形成的字符串。

计算:

$$\sum_{i=1}^n\sum_{j=1}^n\sum_{x=1}^n\sum_{y=1}^n\sum_{p=1}^n\sum_{q=1}^nM(s_i+s_x+s_p,s_j+s_y+s_q)$$

答案对 2642^{64} 取模。

输入格式

从文件 hvd.in\textit{hvd.in} 中读入数据。

第一行一个整数 nn。

接下来 nn 行每行一个字符串。

输出格式

输出到文件 hvd.out\textit{hvd.out} 中。

一行一个整数表示答案。

样例 #1

样例输入 #1

1
a

样例输出 #1

1

i,j,x,y,p,qi,j,x,y,p,q 全部为 11,此时 si+sx+sp=aaas_i+s_x+s_p=\texttt{aaa},sj+sy+sq=aaas_j+s_y+s_q=\texttt{aaa},前者有 11 个子串等于后者。

样例 #2

样例输入 #2

2
a
ab

样例输出 #2

12

样例 #3

样例输入 #3

5
a
aa
aaa
abba
bbab

样例输出 #3

2191

样例 #4

见下发文件中的 hvd/hvd4.in\textit{hvd/hvd4.in} 与 hvd/hvd4.ans\textit{hvd/hvd4.ans}。

该样例满足子任务 44 的限制。

样例 #5

见下发文件中的 hvd/hvd5.in\textit{hvd/hvd5.in} 与 hvd/hvd5.ans\textit{hvd/hvd5.ans}。

该样例满足子任务 55 的限制。

样例 #6

见下发文件中的 hvd/hvd6.in\textit{hvd/hvd6.in} 与 hvd/hvd6.ans\textit{hvd/hvd6.ans}。

该样例满足子任务 66 的限制。

样例 #7

见下发文件中的 hvd/hvd7.in\textit{hvd/hvd7.in} 与 hvd/hvd7.ans\textit{hvd/hvd7.ans}。

该样例满足子任务 77 的限制。

提示

对字符串 ss,设 ∣s∣|s| 为其长度。设 S=∑i=1n∣si∣S=\sum_{i=1}^n|s_i|。

对于 100%100\% 的数据,1≤n,S≤3×1051\leq n,S\leq 3\times 10^5,字符集为所有小写英文字母,字符串互不相同。

子任务 nn SS 字符集 特殊性质
11 ≤5\leq 5 ≤20\leq 20
22 ≤10\leq 10 ≤300\leq 300
33 ≤100\leq 100 ≤5000\leq 5000
44 ≤1000\leq 1000
55 ≤2×105\leq 2\times 10^5 {a}\{\texttt a\}
66 ≤2×105\leq 2\times 10^5 {a,b}\{\texttt a,\texttt b\} A
77 B
88 ≤1000\leq 1000
99 ≤2×105\leq 2\times 10^5
1010 ≤3×105\leq 3\times 10^5
  • 特殊性质 A:字符串的每一个位置从字符集中等概率随机选取。
  • 特殊性质 B:字符串长度 ≤10\leq 10。

评测时开启合理的子任务依赖,每个子任务分值均为 1010 分。