题目大意

P16231 [蓝桥杯 2026 省 A] 基因研究

题目描述

DNA 分子的四种碱基分别记为 A、T、G、C。每个人的基因序列都可以认为是一个由 A、T、G、C 四种字符组成的长度为 $n$ 的字符串。

小蓝正在研究一种疾病。他观察到，这种疾病存在一个固定的易感序列（也可认为是一个由 A、T、G、C 构成的字符串）。若某人的基因序列中存在一个子串恰好等于这个易感序列，则称此人“易感”；若基因序列的任意子串都不等于这个易感序列，则称此人“不易感”。

小蓝希望根据这座城市中人们的基因序列情况，估计出城里“易感”人群所占的比例。

然而，直接获取整座城市中每个人完整的基因序列非常困难。为此，小蓝采用了抽样统计的方法：通过大量采样，他估计出了在这座城市中，每一个位置上碱基为 A、T、G、C 的人数占比。我们可以将其理解为：在所有人的基因序列中，第 $i$ 个位置为 A、T、G、C 的人数占比分别是多少。

为了简化模型，小蓝作出如下假设：对于任意一个人，其基因序列在每个位置上的碱基分布与采样结果完全一致，且不同位置之间的碱基相互独立。也就是说，即使已经确定了若干个位置上的碱基，剩余位置上的碱基仍然按照对应位置的分布独立生成。

现在，小蓝决定将这些概率以模 $998244353$ 的形式算出：如果“易感”人群所占比例为 $\frac{p}{q}$，则小蓝希望得到一个整数 $x$，满足 $x \times q \equiv p \pmod{998244353}$。请你根据给定的易感序列，以及每个位置上四种碱基的概率分布，帮小蓝计算并输出这个整数 $x$。

输入格式

第一行包含两个正整数 $n, m$，分别表示基因序列长度和易感序列长度。

第二行包含一个长度为 $m$ 的字符串 $s$，仅由 A、T、G、C 构成，表示疾病对应的易感序列。

接下来 $n$ 行，每行包含四个非负整数 $a_i, t_i, g_i, c_i$。其中：

• $a_i$ 表示第 $i$ 个位置碱基为 A 的概率（模 $998244353$ 意义下）；

• $t_i$ 表示第 $i$ 个位置碱基为 T 的概率（模 $998244353$ 意义下）；

• $g_i$ 表示第 $i$ 个位置碱基为 G 的概率（模 $998244353$ 意义下）；

• $c_i$ 表示第 $i$ 个位置碱基为 C 的概率（模 $998244353$ 意义下）。

保证对任意 $i$，均有 $(a_i + t_i + g_i + c_i) \bmod 998244353 = 1$。

输出格式

输出一行，包含一个非负整数，表示“基因序列中包含易感序列作为子串”的人群占比在模 $998244353$ 意义下的结果。

输入输出样例 #1

输入 #1

3 2
AA
499122177 499122177 0 0
499122177 0 499122177 0
499122177 0 0 499122177

输出 #1

623902721

说明/提示

【样例说明】

基因序列共有 $3$ 个位置：

• 第 $1$ 位有 $\frac{1}{2}$ 的概率是 $A$，有 $\frac{1}{2}$ 的概率是 $T$；

• 第 $2$ 位有 $\frac{1}{2}$ 的概率是 $A$，有 $\frac{1}{2}$ 的概率是 $G$；

• 第 $3$ 位有 $\frac{1}{2}$ 的概率是 $A$，有 $\frac{1}{2}$ 的概率是 $C$。

易感序列为 $AA$。因此，一个人被视为“易感”，当且仅当其基因序列中包含子串 $AA$。

所有可能产生的基因序列中，满足条件的共有 3 种，分别是 $AAC$、$TAA$ 和 $AAA$。这 3 种序列出现的概率均为 $\frac{1}{8}$，因此“易感”人群所占的总比例为 $\frac{1}{8} + \frac{1}{8} + \frac{1}{8} = \frac{3}{8}$，其在模 $998244353$ 意义下的结果为 $623902721$。

【评测用例规模与约定】

对于 $30\%$ 的数据，$1 \le m \le n \le 5$；

另存在 $20\%$ 的数据，$a_i = t_i = g_i = c_i$；

对于 $100\%$ 的数据，$1 \le m \le n \le 3000, 0 \le a_i, t_i, g_i, c_i < 998244353$。

思路讲解

AI 生成的 latex 题解代码

No content to show

AC代码

源代码

心路历程（WA，TLE，MLE……）