#PQJ1789x8954. QOJ 1789_8954

    ID: 2703 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2022字符串后缀数组前缀和

QOJ 1789_8954

标题: 一般路过串串题 - Problem - QOJ.ac

#8954. 一般路过串串题

Statistics

The problem was used in the following contests:

给定两个字符串 S 和 T。

记 Sl,r 表示 S 的第 l 到第 r 个字符组成的字符串。

定义 Sl,r 的子串为任意满足 l≤x≤y≤r 的 Sx,y。

设 f(l,r) 表示 Sl,r 的所有子串在 T 中出现次数的和。

则你需要计算:

∑i=1|S|∑j=i|S|f(i,j)⋅(j−i+1)2

对 (109+7)取模的结果。

输入格式

从标准输入中读入数据。

输入两行,每行分别读取一个仅包含小写字母的字符串,分别表示 S 和 T。

输出格式

输出到标准输出。

输出一行一个整数,表示题目描述中的式子对 (109+7) 取模的结果。

样例数据

样例 1 输入

aba
ba

样例 1 输出

59

样例 2 输入

ababc
babac

样例 2 输出

1094

样例 3 输入

aaaaa
aa

样例 3 输出

1008

样例 4 输入

arknights
genshinimpact

样例 4 输出

5901

子任务

设 max(|S|,|T|)=n。

  • 子任务 1(10分): 1≤n≤60。
  • 子任务 2(20分): 1≤n≤300。
  • 子任务 3(30分): 1≤n≤2000。
  • 子任务 4(25分): 1≤n≤20000。
  • 子任务 5(15分): 1≤n≤500000。