【MX-S5-T4】魔法少女们
题目背景
原题链接:<https://oier.team/problems/92>。
---
> 祈祷着今后的你的人生,永远都有幸福的“魔法”相伴。
**以下是本题所用记号的约定。**
字符串下标均从 $1$ 开始。
$|S|$ 表示字符串 $S$ 的长度。
$S_i$ 表示字符串 $S$ 的第 $i$ 个字符。
记字符串 $S$ 为 $T$ 的前缀,当且仅当:
- $|S|\leq |T|$,
- $\forall i\in[1,|S|]$,$S_i=T_i$。
记字符串 $S$ 为 $T$ 的后缀,当且仅当:
- $|S|\leq |T|$,
- $\forall i\in[1,|S|]$,$S_{|S|-i+1}=T_{|T|-i+1}$。
合法括号序列的定义如下:
- 空串是合法括号序列。
- 若 $A$ 为合法括号序列,则 $(A)$ 为合法括号序列。
- 若 $A,B$ 为合法括号序列,则 $AB$ 为合法括号序列。
题目描述
千和有 $n$ 个**括号序列**,分别是 $S_1,S_2,S_3,\dots,S_n$。
小黑有 $m$ 个**括号序列**,分别是 $T_1,T_2,T_3,\dots,T_m$。
对一个括号序列 $A$,$f(A)$ 为满足以下条件的正整数对 $(i,j)$ 对数:
- $i\in[1,n]$,$j\in [1,m]$;
- $S_i$ 是 $A$ 的**前缀**且 $T_j$ 是 $A$ 的**后缀**。
她们想知道对于所有长度为偶数 $k$ 的**合法括号序列** $S$,$f(S)$ 的和。答案对 $10^9+7$ 取模。
输入输出格式
输入格式
第一行,一个正整数 $c$,表示测试点编号。特殊地,对样例,$c=0$。
第二行,三个正整数 $n,m,k$,其中 $k$ 为偶数。
接下来 $n$ 行,每行一个字符串 $S_i$。
接下来 $m$ 行,每行一个字符串 $T_j$。
输出格式
仅一行,一个自然数,表示答案对 $10^9+7$ 取模后的值。
输入输出样例
输入样例 #1
0
1 2 6
(
()
())
输出样例 #1
4
说明
**【样例解释 #1】**
长度为 $6$ 的合法括号序列有 `()()()`、`()(())`、`(())()`、`(()())`、`((()))`,分别记作 $S_1,S_2,S_3,S_4,S_5$,答案为 $f(S_1)+f(S_2)+f(S_3)+f(S_4)+f(S_5)=1+1+1+1+0=4$。
**【样例 #2】**
见附件中的 `bracket/bracket2.in` 与 `bracket/bracket2.ans`。
该组样例满足测试点 $1\sim 2$ 的约束条件。
**【样例 #3】**
见附件中的 `bracket/bracket3.in` 与 `bracket/bracket3.ans`。
该组样例满足测试点 $3\sim 4$ 的约束条件。
**【样例 #4】**
见附件中的 `bracket/bracket4.in` 与 `bracket/bracket4.ans`。
该组样例满足测试点 $14\sim 15$ 的约束条件。
**【样例 #5】**
见附件中的 `bracket/bracket5.in` 与 `bracket/bracket5.ans`。
该组样例满足测试点 $20\sim 21$ 的约束条件。
**【数据范围】**
对于所有测试数据,保证 $1\leq n,m\leq 2\times 10^5$,$1\leq \vert S_i\vert,\vert T_j\vert\leq \min(k,5\times 10^5)$,$1\leq \sum \vert S_i\vert,\sum \vert T_j\vert\leq 10^7$,$2\leq k\leq 10^6$,$k$ 为偶数。
| 测试点编号 | $n,m\leq$ | $\vert S_i\vert,\vert T_j\vert\leq$ | $\sum \vert S_i\vert,\sum \vert T_j\vert\leq$ | $k\leq$ | 特殊性质 |
| :----------: | :--------------: | :-----------------------------------: | :---------------------------------------------: | :-------------: | :--------: |
| $1\sim2$ | $10$ | $10$ | $100$ | $15$ | 无 |
| $3\sim4$ | $50$ | $100$ | $5\times10^3$ | $100$ | 无 |
| $5\sim8$ | $250$ | $5\times10^3$ | $5\times10^5$ | $5\times10^3$ | 无 |
| $9\sim11$ | $5\times 10^3$ | $10^5$ | $5\times10^5$ | $2\times10^5$ | 无 |
| $12\sim13$ | $5\times10^4$ | $10^5$ | $5\times10^5$ | $2\times10^5$ | A |
| $14\sim15$ | $5\times10^4$ | $10^5$ | $5\times10^5$ | $2\times10^5$ | B |
| $16\sim17$ | $10^5$ | $2\times10^3$ | $10^6$ | $2\times10^5$ | C |
| $18\sim19$ | $10^5$ | $10^5$ | $10^6$ | $2\times10^5$ | C |
| $20\sim21$ | $10^5$ | $10^5$ | $10^6$ | $2\times10^5$ | 无 |
| $22\sim23$ | $2\times10^5$ | $5\times 10^5$ | $10^7$ | $10^6$ | C |
| $24\sim25$ | $2\times10^5$ | $5\times 10^5$ | $10^7$ | $10^6$ | 无 |
* 特殊性质 A:$k<\min\vert S_i\vert+\min\vert T_j\vert$;
* 特殊性质 B:保证 $S_i,T_j$ 是合法的括号序列;
* 特殊性质 C:$k\geq\max\vert S_i\vert+\max\vert T_j\vert$。