题意

给定$m$个长度为$n$的字符串，记$s$，且$s_{i,j} \in [A,C,G,T,?]$

随机构建一个仅含$[A,C,G,T]$的长度为$n$的字符串$t$

求$t$能和其中任意一个$s_i$匹配的概率

$t$和$s_i$匹配定义为存在一种将$s_i$的?转换的方式使得$s_i=t$

$1 \leq n \leq 100$ , $1 \leq m \leq 40$

概率允许$5\%$的误差，注意$P=0$不合法

Solution

因为分母过于强大($4^{100}$)，正经的概率计算大概率会出问题。

注意到概率误差非常宽松，我们可以乱搞抽样调查

一个$t$的贡献可以视为对第一个与$t$匹配的$s_i$贡献$+1$

所以对于每一个$s_i$，构造若干个和$s_i$匹配的$t$，对$s_i$造成贡献仅当$t$和$s_i$匹配但不和$s_{1...i-1}$匹配

设样本空间大小为$k$，随机构造能和$s_i$匹配的概率为$p_1$，造成贡献的样本数量为$f$，则总贡献为

$\frac{p_1 \times f}{k}$

code

#include<bits/stdc++.h>
using namespace std;
const int mxn=110;
typedef long double ldb;
void cal_t(string a);
bool check(string a,string b);
int n,m;
string s[mxn];
string ver="ACGT";
string t;
ldb val[mxn];
ldb ans;
int main()
{
    srand(time(NULL));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) cin>>s[i];
    for(int i=1;i<=m;i++)
    {
        ldb u=0,v=1;
        bool flag=0;
        for(int j=0;j<n;j++) if(s[i][j]!='?') v/=4.0;
        for(int p=1;p<=6123;p++)
        {
            cal_t(s[i]);
            flag=0;
            for(int k=1;k<i;k++)
            {
                if(check(s[k],t)) 
                {
                    flag=1;
                    break;
                }
            }
            if(!flag) u+=1.0;
        }
        ans=ans+(u*v/6123.0);
    }
    printf("%.80Lf\n",ans);
}

bool check(string a,string b)
{
    for(int i=0;i<n;i++)
    {
        if(a[i]=='?') continue;
        if(a[i]!=b[i]) return false;
    }
    return true;
}

void cal_t(string a)
{
    t="";
    for(int i=0;i<n;i++)
    {
        char in;
        if(a[i]=='?') in=char(ver[(rand()%4)]);
        else in=char(a[i]);
        t+=in;
    }
}