题目详情题解（0）讨论（0）提交记录（0）

AT_abc353_e.[ABC353E] Yet Another Sigma Problem

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

对于字符串 x,yx, y，定义 f(x,y)f(x, y) 如下：

  • f(x,y)f(x, y) 为 x,yx, y 的最长公共前缀的长度。

给定 NN 个仅由小写英文字母组成的字符串 (S1,…,SN)(S_1, \ldots, S_N)。请计算下式的值：

∑i=1N−1∑j=i+1Nf(Si,Sj)\sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i, S_j)

输入格式

输入以如下格式从标准输入读入：

NN S1S_1 S2S_2 …\ldots SNS_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

    3
ab abc arc

    输出#1

    4

  • 输入#2

    11
ab bb aaa bba baba babb aaaba aabbb a a b

    输出#2

    32

说明/提示

限制条件

  • 2≤N≤3×1052 \leq N \leq 3 \times 10^5
  • SiS_i 为仅由小写英文字母组成的字符串
  • 1≤∣Si∣1 \leq |S_i|
  • ∣S1∣+∣S2∣+…+∣SN∣≤3×105|S_1| + |S_2| + \ldots + |S_N| \leq 3 \times 10^5
  • 输入的所有数值均为整数

样例解释 1

  • f(S1,S2)=2f(S_1, S_2) = 2
  • f(S1,S3)=1f(S_1, S_3) = 1
  • f(S2,S3)=1f(S_2, S_3) = 1

因此，答案为 f(S1,S2)+f(S1,S3)+f(S2,S3)=4f(S_1, S_2) + f(S_1, S_3) + f(S_2, S_3) = 4。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页