#P15804. [中国国家队2025年林芝集训]计数题

    ID: 15015 传统题 8000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>字符串数学动态规划数据结构线段树CF3500

[中国国家队2025年林芝集训]计数题

题目描述

先考虑如下问题 A。

给定两个由字符 A、B、? 构成的字符串 P,QP,Q。

对于每一种将 P,QP,Q 中所有 ? 分别替换成 A 或 B 的方案,记替换后的两个字符串为 P′,Q′P',Q'。

接着枚举所有有序二元组 (X,Y)(X,Y),其中 X,YX,Y 均为非空二进制串,并且满足

1≤∣X∣,∣Y∣≤n.1\le |X|,|Y|\le n.

将 P′,Q′P',Q' 中的字符 A 全部替换成二进制串 XX,将字符 B 全部替换成二进制串 YY。如果替换完成后,两个字符串完全相同,则计入一种合法方案。

问题 A 要求求出所有合法方案数之和,并对 109+710^9+7 取模。

形式化地,设 rep⁡(R,X,Y)\operatorname{rep}(R,X,Y) 表示将字符串 RR 中的每个 A 替换为 XX,每个 B 替换为 YY 后得到的二进制串。则问题 A 的答案为

$$\sum_{P',Q'}\ \sum_{\substack{X,Y\in{0,1}^+\1\le |X|,|Y|\le n}} \left[ \operatorname{rep}(P',X,Y)=\operatorname{rep}(Q',X,Y) \right],$$

其中外层求和枚举所有由 P,QP,Q 中的 ? 替换得到的字符串 P′,Q′P',Q',方括号 [⋅][\cdot] 表示若条件成立则取值为 11,否则取值为 00。

现在,给你两个由 A、B、? 构成的字符串 S,TS,T,并有 qq 次修改操作。每次修改后,你需要求出当前 S,TS,T 对应的问题 A 的答案。

每次修改形如:

opt x c
  • 若 opt=0opt=0,则将 SxS_x 修改为字符 cc;
  • 若 opt=1opt=1,则将 TxT_x 修改为字符 cc。

其中 c∈A,B,?c\in{\texttt{A},\texttt{B},\texttt{?}}。

字符串下标从 11 开始。

输入格式

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

第二行包含一个字符串 SS。

第三行包含一个字符串 TT。

第四行包含一个正整数 qq。

接下来 qq 行,每行包含两个非负整数和一个字符:

opt x c

表示一次修改操作。

输出格式

输出 qq 行,每行一个整数,表示每次修改后的答案。

答案需要对 109+710^9+7 取模。

样例 1

输入

1 2 3
?
?B
1
0 1 ?

输出

2

样例 2

输入

1 1 8
A
?
1
0 1 B

输出

260610

样例 3

输入

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

输出

6
6
20
26
32
94
38
50
50
50

样例 4

输入

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

输出

4366
292
168
62

样例 5

输入

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

输出

30
126
6

数据范围

对于 100100% 的数据:

  • ∣S∣,∣T∣,n≤106|S|,|T|,n\le 10^6;
  • q≤6×103q\le 6\times 10^3;
  • ∣∣S∣−∣T∣∣≤10\bigl||S|-|T|\bigr|\le 10;
  • opt∈0,1opt\in{0,1};
  • 当 opt=0opt=0 时,1≤x≤∣S∣1\le x\le |S|;
  • 当 opt=1opt=1 时,1≤x≤∣T∣1\le x\le |T|;
  • c∈A,B,?c\in{\texttt{A},\texttt{B},\texttt{?}}。

子任务

子任务编号 分值 S,TS,T 长度上限 nn 上限 qq 上限 特殊性质
1 6 44 11 无
2 3 10610^6 BCD
3 BCE
4 CD
5 CE
6 ABD
7 ABE
8 9 10210^2 无
9 8 5×1035\times 10^3
10 7 10610^6 10610^6 D
11 E
12 3 无
13 7 100100
14 9 6×1036\times 10^3 F
15 11 10510^5 10310^3 无
16 6 10610^6 6×1036\times 10^3 D
17 E
18 3 无

特殊性质说明:

  • 特殊性质 A:修改后,S,TS,T 中不含 A;
  • 特殊性质 B:修改后,S,TS,T 中不含 B;
  • 特殊性质 C:修改后,S,TS,T 中不含 ?;
  • 特殊性质 D:∣S∣=∣T∣|S|=|T|;
  • 特殊性质 E:∣S∣≠∣T∣|S|\ne |T|;
  • 特殊性质 F:若 opt=0opt=0,则修改前 SxS_x 不为 ?;若 opt=1opt=1,则修改前 TxT_x 不为 ?;并且 cc 不为 ?。

对于特殊性质 A、B、C,保证 q=1,opt=0,x=1,c=S1q=1,opt=0,x=1,c=S_1。