#1924. 基因组重构
基因组重构
基因组重构
题目描述
标题: 基因组重构 - Problem - QOJ.ac
#10359. 基因组重构
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