#1831. 一般路过串串题

    ID: 1831 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1789来源:qoj.ac数据:公开样例字符串后缀数组前缀和

一般路过串串题

一般路过串串题

题目描述

标题: 一般路过串串题 - 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。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

aba
ba
59

样例 2

ababc
babac
1094