#2250. 计数题

计数题

计数题

题目描述

标题: 计数题 - Problem - QOJ.ac

#17582. 计数题

Statistics

The problem was used in the following contests:

题目描述

问题 A:给两个由 A,B,? 构成的串,对于将每个 ? 替换为 A 或 B 的任意方案,对所有长度 ∈[1,n] 的 01 串形成的二元组 (S,T) 求,把 A 换成 S,B 换成 T 后两串相等的方案数之和,对 109+7 取模。

现在,给你两个由 A,B,? 构成的串 S,T,有 q 次询问,每次给定 opt,x,c。opt=0 时将 Sx 修改为 c,opt=1 时将 Tx 修改为 c。对于每次修改后的 S,T,求出问题 A 的答案。

输入格式

第一行三个正整数 |S|,|T|,n。

第二行一个字符串 S。

第三行一个字符串 T。

第四行一个正整数 q。

接下来 q 行每行两个非负整数与一个 A,B,? 中的字符 opt,x,c。

输出格式

q 行,每行一个正整数,表示答案。

样例一

input

1 2 3
?
?B
1
0 1 ?

output

2

样例二

input

1 1 8
A
?
1
0 1 B

output

260610

样例三

input

4 6 6
AABA
BBB?AB
10
1 4 A
1 3 ?
0 3 A
1 1 ?
1 6 ?
1 5 ?
0 2 B
0 3 ?
1 3 ?
0 4 B

output

6
6
20
26
32
94
38
50
50
50

样例四

input

3 3 5
A??
?AB
4
0 1 B
0 2 B
0 3 A
1 1 A

output

4366
292
168
62

样例五

input

3 5 13
ABA
BABBA
3
1 5 B
0 2 A
1 2 B

output

30
126
6

限制与约定

对于 100% 的数据:|S|,|T|,n≤106,q≤6×103,||S|−|T||≤10,opt∈{0,1},opt=0 时 1≤x≤|S|,opt=1 时 1≤x≤|T|,c∈{A,B,?}。

子任务编号 分值 |S|,|T|≤ n≤ q≤ 特殊性质 1 6 4 4 1 无 2 3 106 106 1 BCD 3 3 106 106 1 BCE 4 3 106 106 1 CD 5 3 106 106 1 CE 6 3 106 106 1 ABD 7 3 106 106 1 ABE 8 9 102 102 1 无 9 8 5×103 5×103 1 无 10 7 106 106 1 D 11 7 106 106 1 E 12 3 106 106 1 无 13 7 106 106 100 无 14 9 106 106 6×103 F 15 11 106 105 103 无 16 6 106 106 6×103 D 17 6 106 106 6×103 E 18 3 106 106 6×103 无

  • 特殊性质 A:修改后,S,T 中不含 A;
  • 特殊性质 B:修改后,S,T 中不含 B;
  • 特殊性质 C:修改后,S,T 中不含 ?;
  • 特殊性质 D:|S|=|T|;
  • 特殊性质 E:|S|≠|T|;
  • 特殊性质 F:opt=0 时 Sx 不为 ?,opt=1 时 Tx 不为 ?,c 不为 ?。

对于特殊性质 ABC,保证 q=1,opt=0,x=1,c=S1。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1 2 3
?
?B
1
0 1 ?
2

样例 2

1 1 8
A
?
1
0 1 B
260610