#P15595. [2025年山东第一轮集训] 字符串

    ID: 14807 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>字符串AC自动机数据结构树状数组算法基础数学模拟CF2700

[2025年山东第一轮集训] 字符串

题目描述

给定 nn 个字符串

s1,s2,…,sn,s_1,s_2,\ldots,s_n,

保证它们互不相同。请求出满足如下条件的三元组 (i,j,k)(i,j,k) 的个数:

  • 1≤i,j,k≤n1\le i,j,k\le n,且 i,j,ki,j,k 互不相同;
  • sis_i 是 sjs_j 的子串,sjs_j 是 sks_k 的子串;
  • 不存在一个 j′∉{i,j,k}j'\notin\{i,j,k\},使得 sis_i 是 sj′s_{j'} 的子串且 sj′s_{j'} 是 sks_k 的子串。

输入格式

第一行,一个正整数 nn。

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

输出格式

一行,一个非负整数,表示答案。

样例 1 输入

4
ababa
baka
abab
ab

样例 1 输出

1

样例 2 输入

5
bc
cbcb
cbca
cbc
c

样例 2 输出

3

数据范围与子任务

记

L=∑i=1n∣si∣.L=\sum_{i=1}^{n}|s_i|.

对于所有数据:

1≤n≤5×105,1\le n\le 5\times 10^5, 1≤L≤106,1\le L\le 10^6,

所有 sis_i 都是仅由小写字母组成的非空字符串。

子任务 n≤n\le L≤L\le 特殊性质 分值
1 500500 无 10
2 50005000 10410^4 25
3 5×1055\times 10^5 10610^6 A 15
4 10510^5 2×1052\times 10^5 B 20
5 5×1055\times 10^5 10610^6 无 30

特殊性质 A:保证所有 sis_i 均仅由 a、b 组成,且每个 sis_i 中恰有一个 b。

特殊性质 B:保证所有 sis_i 均仅由 a、b 组成。