浅谈概率 DP 在生物分离定律题中的运用
Little_Zyl · · 学习·文化课
前言
最近刚学习了概率
正文
先来看一道题：
上图为某单基因遗传病的遗传系谱图（方块为男性，圆圈为女性，黑色为患者，白色为正常人）。问：若
现在我们用概率
先对图中的点重新标号，并加上最后那个女孩：
设
开始分类讨论：（以下用
对于没有给出父母的人，有如下几种情况：
- 若
u 节点所表示的人患病，则 Ta 的基因型一定为aa ； - 若
u 节点所表示的人正常，且 Ta 的子女中有患病的，则 Ta 的基因型一定为Aa ； - 若
u 节点所表示的人正常，且 Ta 的子女中没有患病的，则 Ta 的基因型有{\large \frac{1}{2}} 的概率为AA ，有{\large \frac{1}{2}} 的概率为Aa ； - 若不知道
u 节点所表示的人的表现型，则 Ta 的基因型为AA,Aa,aa 的概率都为{\large \frac{1}{3}} 。
对于给出了父母的人就需要状态转移方程了。根据生物学知识可得：（以下
于是可推出状态转移方程为：
另外，若知道这个人的表型，则需要进行如下操作：
- 若
u 节点所表示的人患病，则将dp_{u,AA} 和dp_{u,Aa} 置为0 ； - 若
u 节点所表示的人正常，且 Ta 的子女中有患病的，则将dp_{u,AA} 和dp_{u,aa} 置为0 ； - 若
u 节点所表示的人正常，且 Ta 的子女中没有患病的，则将dp_{u,aa} 置为0 。
处理完上面三条后还需进行“归
然后，我们发现系谱图可以看作一个
最后，通过手动模拟， 把代码打出来，跑一遍，就能得到此题答案为
::::success[屎山代码]
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int gcd(int a, int b){
a=abs(a),b=abs(b);
return b?gcd(b,a%b):a;
}
struct fs{
int a, b;
fs(int a_=0,int b_=1):a(a_),b(b_){
if(b<0)a=-a,b=-b;
int g=gcd(a,b);
if(g!=0)a/=g,b/=g;
if(a==0)b=1;
}
friend fs operator+(const fs&x,const fs&y){return fs(x.a*y.b+y.a*x.b,x.b*y.b);}
friend fs operator*(const fs&x,const fs&y){return fs(x.a*y.a,x.b*y.b);}
friend fs operator/(const fs&x,const fs&y){
if(y.a==0)cerr<<"Error: division by zero\n",exit(1);
return fs(x.a*y.b,x.b*y.a);
}
friend ostream&operator<<(ostream&os,const fs&o){
os<<o.a<<"/"<<o.b;return os;
}
}dp[N][3];//0:AA 1:Aa 2:aa
int n,m,a[N],P1[N],P2[N],hp[N],bj[N],deg[N];
vector<int>G[N];
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
for(int i=1,u;i<=m;i++){
cin>>u,cin>>P1[u]>>P2[u],deg[u]=2,hp[u]=1;
G[P1[u]].push_back(u),G[P2[u]].push_back(u);
if(a[u]==1)bj[P1[u]]=bj[P2[u]]=1;
}
queue<int>q;
for(int i=1;i<=n;i++)if(!deg[i])q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
for(int v:G[u])if(!--deg[v])q.push(v);
if(a[u]==1)dp[u][2]=fs(1),dp[u][0]=dp[u][1]=fs(0);
else if(bj[u]==1)dp[u][1]=fs(1),dp[u][0]=dp[u][2]=fs(0);
else if(!hp[u]){
if(a[u]==0)dp[u][0]=dp[u][1]=fs(1,2),dp[u][2]=fs(0);
if(a[u]==2)dp[u][0]=dp[u][1]=dp[u][2]=fs(1,3);
}else{
fs *dp1=dp[P1[u]],*dp2=dp[P2[u]];
dp[u][0]=(dp1[0]*dp2[0])+(fs(1,2)*dp1[0]*dp2[1])+(fs(1,2)*dp1[1]*dp2[0])+(fs(1,4)*dp1[1]*dp2[1]);
dp[u][2]=(dp1[2]*dp2[2])+(fs(1,2)*dp1[2]*dp2[1])+(fs(1,2)*dp1[1]*dp2[2])+(fs(1,4)*dp1[1]*dp2[1]);
dp[u][1]=(dp1[0]*dp2[2])+(dp1[2]*dp2[0])+(fs(1,2)*dp1[1]*dp2[1])+
(fs(1,2)*dp1[0]*dp2[1])+(fs(1,2)*dp1[1]*dp2[0])+(fs(1,2)*dp1[2]*dp2[1])+(fs(1,2)*dp1[1]*dp2[2]);
if(!a[u]){
dp[u][2]=fs(0);
if(dp[u][0].a==0)dp[u][1]=fs(1);
else if(dp[u][1].a==0)dp[u][0]=fs(1);
else{
fs t=dp[u][0]+dp[u][1];
dp[u][0]=dp[u][0]/t,dp[u][1]=dp[u][1]/t;
}
// cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<"\n";
}
}
}
cout<<dp[n][1];
return 0;
}
/*
输入格式：
第一行一个整数n，表示节点数
第二行n个整数(0,1,2)，第i个表示编号为i的人为正常(0)，患病(1)，未知(2)
第一行一个整数m，表示家庭关系数
接下来m行，每行三个整数u,p1,p2，表示p1,p2分别为u的爸和妈
*/
/*
input:
16
0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0
9
7 1 2
8 1 2
9 1 2
10 3 4
13 9 10
12 5 6
14 11 12
15 11 12
16 13 14
output:
13/27
*/::::
总结
实际上，用概率