1637: [STT2024Nov] 三花遗传性测试
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：5
解决：3
题目描述
### 题目背景
三花猫 XXY 是一只三花猫。
由小学科学知识可知，三花猫的三花性状是由基因决定的。而三花性状的基因在 X 染色体上，且呈隐形，故只有两个 X 染色体都含有三花基因，才会呈现三花猫的性状，因此三花猫通常情况下都是母猫。
染色体由 DNA 和蛋白质构成，基因存在于 DNA 上，DNA 由腺嘌呤(A)、胞嘧啶(C)、鸟嘌呤(G)和胸腺嘧啶(T)构成。
### 题目描述
现有公母两只猫，地地已经通过智能生物检测仪获得了这两只猫性染色体上 DNA 的组成。并且，地地手上已有三花基因的信息。
三花基因的长度为 $n$，所有性染色体上 DNA 的长度均为 $m$。三花基因和性染色体 DNA 均由`ACGT`组成。
称一个 DNA 含有三花基因，当且仅当三花基因是此 DNA 序列的子串。
现在，地地想知道这两只猫后代为三花猫的概率为多少。
给出两只猫的基因状况（先公后母），问它们生出三花猫的概率是多少。
三花猫 XXY 是一只三花猫。
由小学科学知识可知，三花猫的三花性状是由基因决定的。而三花性状的基因在 X 染色体上，且呈隐形，故只有两个 X 染色体都含有三花基因，才会呈现三花猫的性状，因此三花猫通常情况下都是母猫。
染色体由 DNA 和蛋白质构成，基因存在于 DNA 上，DNA 由腺嘌呤(A)、胞嘧啶(C)、鸟嘌呤(G)和胸腺嘧啶(T)构成。
### 题目描述
现有公母两只猫，地地已经通过智能生物检测仪获得了这两只猫性染色体上 DNA 的组成。并且，地地手上已有三花基因的信息。
三花基因的长度为 $n$，所有性染色体上 DNA 的长度均为 $m$。三花基因和性染色体 DNA 均由`ACGT`组成。
称一个 DNA 含有三花基因，当且仅当三花基因是此 DNA 序列的子串。
现在，地地想知道这两只猫后代为三花猫的概率为多少。
给出两只猫的基因状况（先公后母），问它们生出三花猫的概率是多少。
输入
第一行，两个整数 $n, m$，分别表示三花基因长度和染色体上 DNA 长度。
第二行，一串由`ACGT`组成的长度为 $n$ 的字符串 $\Omega$，表示三花基因。
接下来四行，每行有一个字符 $Z_i$ 和一串由`ACGT`组成的长度为 $m$ 的字符串 $\mho_i$，分别表示性染色体类型和这个染色体的 DNA。
第二行，一串由`ACGT`组成的长度为 $n$ 的字符串 $\Omega$，表示三花基因。
接下来四行，每行有一个字符 $Z_i$ 和一串由`ACGT`组成的长度为 $m$ 的字符串 $\mho_i$，分别表示性染色体类型和这个染色体的 DNA。
输出
输出生出三花猫的概率（单位：百分比），保留两位小数。
样例输入 复制
3 5
AAT
X AATCA
Y ACCGT
X GGATC
X GAATA样例输出 复制
25.00%提示
**【样例 #1 解释】**
设公猫的性染色体为 $X_0Y$，母猫的性染色体为 $X_1X_2$
可知 $X_0$ 与 $X_2$ 均含有三花基因。
两只猫生出的猫可能有以下四种情况：
- $X_1Y$
为公猫，并无三花猫可能。
- $X_2Y$
为公猫，并无三花猫可能。
- $X_1X_0$
为母猫，但仅 $X_0$ 含有三花基因，故不为三花猫。
- $X_2X_0$
为母猫，$X_2$ 和 $X_0$ 均含有三花基因，故为三花猫。
综上，这两只猫生出三花猫的概率为 $25\%$
**【数据范围】**
对于 $50\%$ 的数据，$1 \leq n \leq m \leq 20$。
对于 $100\%$ 的数据，$1 \leq n \leq m \leq 10^3$，$Z_i \in \{X, Y\}$，且保证构成 $\Omega$ 和 $\mho_i$ 的字符只可能是 $\{A, C, G, T\}$ 中的一个。
设公猫的性染色体为 $X_0Y$，母猫的性染色体为 $X_1X_2$
可知 $X_0$ 与 $X_2$ 均含有三花基因。
两只猫生出的猫可能有以下四种情况：
- $X_1Y$
为公猫，并无三花猫可能。
- $X_2Y$
为公猫，并无三花猫可能。
- $X_1X_0$
为母猫，但仅 $X_0$ 含有三花基因，故不为三花猫。
- $X_2X_0$
为母猫，$X_2$ 和 $X_0$ 均含有三花基因，故为三花猫。
综上，这两只猫生出三花猫的概率为 $25\%$
**【数据范围】**
对于 $50\%$ 的数据，$1 \leq n \leq m \leq 20$。
对于 $100\%$ 的数据，$1 \leq n \leq m \leq 10^3$，$Z_i \in \{X, Y\}$，且保证构成 $\Omega$ 和 $\mho_i$ 的字符只可能是 $\{A, C, G, T\}$ 中的一个。