遗传学概率计算与动态规划实现

伊凹遥

1. 题目背景与遗传学基础解析

这道题目将编程与遗传学知识巧妙结合，考察了孟德尔遗传规律的概率计算。我们先要理解题目中的遗传学背景：

基因型表示：0=aa（纯合隐性），1=Aa（杂合子），2=AA（纯合显性）
显隐性关系：A对a是完全显性，因此AA和Aa表现为双眼皮（显性性状），aa表现为单眼皮（隐性性状）
交配规则：两个个体交配时，各自随机提供一个等位基因组成子代基因型

理解交配产生的概率分布是关键。例如：

AA × AA → 100% AA
AA × Aa → 50% AA + 50% Aa
Aa × Aa → 25% AA + 50% Aa + 25% aa

2. 动态规划解法设计

2.1 状态定义与转移

我们定义f[i][j]表示处理到第i个个体时，当前子代基因型为j的概率（j∈{0,1,2}）。初始状态f[0][a[0]] = 1，即初始基因型确定为a[0]。

状态转移需要考虑三种情况（对应a[i]的三种取值）：

当a[i]=0（aa）时：
- 与AA交配：100% Aa
- 与Aa交配：50% Aa + 50% aa
- 与aa交配：100% aa
当a[i]=1（Aa）时：
- 与AA交配：50% AA + 50% Aa
- 与Aa交配：25% AA + 50% Aa + 25% aa
- 与aa交配：50% Aa + 50% aa
当a[i]=2（AA）时：
- 与AA交配：100% AA
- 与Aa交配：50% AA + 50% Aa
- 与aa交配：100% Aa

2.2 模运算处理

题目要求结果对998244353取模，且涉及分数运算。我们需要使用模逆元来表示分数：

1/2 ≡ 499122177 (mod 998244353)
1/4 ≡ 748683265 (mod 998244353)

快速幂求逆元的实现：

cpp复制int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

3. 代码实现详解

3.1 初始化与输入处理

cpp复制constexpr int N = 5e6 + 5, mod = 998244353, inv = 499122177;
int f[N][3], a[N], n;

// 输入处理
cin >> n >> a[0];
f[0][a[0]] = 1; // 初始基因型确定

3.2 核心状态转移

针对三种基因型分别处理：

cpp复制rep(i,n) {
    cin >> a[i];
    rpt(j,0,2) f[i][j] = f[i-1][j]; // 继承上一状态
    
    if(!a[i]) { // aa型
        f[i][0] = (f[i][0] + f[i-1][0] + f[i-1][1] * inv) % mod;
        f[i][1] = (f[i][1] + f[i-1][2] + f[i-1][1] * inv) % mod;
    }
    else if(a[i] & 1) { // Aa型
        f[i][0] = (f[i][0] + f[i-1][0] * inv + f[i-1][1] * inv % mod * inv) % mod;
        f[i][1] = (f[i][1] + f[i-1][0] * inv + f[i-1][1] * inv + f[i-1][2] * inv) % mod;
        f[i][2] = (f[i][2] + f[i-1][2] * inv + f[i-1][1] * inv % mod * inv) % mod;
    }
    else { // AA型
        f[i][2] = (f[i][2] + f[i-1][2] + f[i-1][1] * inv) % mod;
        f[i][1] = (f[i][1] + f[i-1][0] + f[i-1][1] * inv) % mod;
    }
}

3.3 结果计算与输出

最终结果是所有子序列产生显性性状的概率之和除以子序列总数：

cpp复制f[n][a[0]] = (f[n][a[0]] - 1 + mod) % mod; // 减去初始状态
int ans = (f[n][1] + f[n][2]) * qpow(qpow(2,n) - 1, mod - 2) % mod;
cout << ans;

4. 算法优化与注意事项

4.1 空间优化

原始实现使用O(n)空间，可以优化为O(1)空间：

cpp复制int cur[3] = {0}, next[3] = {0};
cur[a[0]] = 1;

rep(i,n) {
    cin >> a[i];
    copy(cur, cur+3, next);
    
    // 状态转移逻辑相同
    // ...
    
    copy(next, next+3, cur);
}