#1924. 基因组重构

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

基因组重构

基因组重构

题目描述

标题: 基因组重构 - Problem - QOJ.ac

#10359. 基因组重构

Statistics

The problem was used in the following contests:

题目描述

生物学家小 T 最近在研究合成基因串的课题,所谓基因串就是字符集为 {A,C,G,T} 的字符串。
对于一次研究,对象是 3 个基因串 X,Y,Z。小 T 会从 X 中选出一个任意连续子串 X1,从 Y 中选出一个任意连续子串 Y1,从 Z 中选出一个任意连续子串 Z1,然后按顺序拼接它们得到 X1+Y1+Z1。设 f(X,Y,Z) 为这样能组成多少不同的基因串。(注意以上的任意连续子串都可以是空串)

现在小 T 有 3 个长度为 n的基因串 A,B,C 和 Q 次研究,每次研究由 6 个正整数 Al,Ar,Bl,Br,Cl,Cr 描述,表示她需要求 f(A[Al:Ar],B[Bl:Br],C[Cl:Cr])mod998244353 的值。

输入格式

第一行两个正整数 n,Q。

接下来三行,每行一个长度为 n 的字符集为 {A,C,G,T} 的字符串,表示基因串 A,B,C。

接下来 Q 行,每行 6 个正整数 Al,Ar,Bl,Br,Cl,Cr,描述一次询问。

输出格式

输出 Q 行,每行一个非负整数,表示答案。

样例

样例输入一

2 1
AC
CC
AA
1 2 1 2 1 1

样例输出一

15

样例输入二

3 1
ACG
GCA
TTT
1 3 1 3 2 1

样例输出二

35

样例说明

如果 l>r,则 S[l:r] 是空串,空串是空串的连续子串。

限制与约定

  • 对于 100% 的数据,有 n,Q≤105,1≤Al,Ar,Bl,Br,Cl,Cr≤n
  • 定义限制 1 为:对于所有询问有 Bl>Br 且 Cl>Cr
  • 定义限制 2 为:对于所有询问有 Cl>Cr

编号 n Q 其他限制 1 10 10 2 20 20 3 50 50 4 100 100 5 100 100 6 500 500 7 500 500 8 100 100000 9 250 100000 10 3000 100000 11 3000 100000 限制 1 12 3000 100000 限制 2 13 5000 5000 限制 1 14 5000 5000 限制 2 15 5000 5000 16 50000 50000 限制 2 17 100000 100000 限制 1 18 50000 50000 19 70000 70000 20 100000 100000

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 1
AC
CC
AA
1 2 1 2 1 1
15

样例 2

3 1
ACG
GCA
TTT
1 3 1 3 2 1
35