给定 \(m\) 个长度为 \(n\) 且由 \(\texttt{AGCT?}\) 五种字符组成的字符串 \(s_i\)。
你需要求出由 \(\texttt{AGCT}\) 四种字符组成的随机字符串，能够匹配 \(\{s_1,s_2,\dots,s_m\}\) 中的至少一个字符串的概率。
你的答案与实际答案相对误差不能超过 \(5 \%\)。
\(1 \leq n \leq 100\)，\(1 \leq m \leq 30\)。
这个问题看起来很不可做，考虑直接随机化。
我们每次随机一个字符串，可以在 \(O(nm)\) 的时间复杂度内求出每个字符串的匹配情况。
如果我们使用这种方法，相对误差会很大，这很不牛。
考虑答案更加准确的暴力。我们考虑钦定需要匹配的字符串，进行容斥即可，这样的时间复杂度是 \(O(nm \times 2^m)\) 的。
我们考虑将 \(m\) 个字符串分成两部分，对左右两边暴力做一遍，再减去同时匹配两边的概率。
这样就直接随机字符串了，准确率会大大提升。
#include<iostream>
#include<cstdio>
#include<random>
#include<ctime>
using namespace std;
mt19937 rnd(time(0));
char ch[40][110],tmp[110];
double ans[1<<15];
double p1,p2,p3;
int main(){int n,m;scanf("%d %d",&n,&m);for(int i=0;i<m;i++){for(int j=1;j<=n;j++){cin>>ch[i][j];}}int mid=m>>1;int l_len=mid,r_len=m-mid;for(int i=0;i<(1<<l_len);i++){int cnt=0;bool ok=true;for(int j=1;j<=n;j++){cnt++;int flag1=0,flag2=0,flag3=0,flag4=0;for(int k=0;k<l_len;k++){if(i&(1<<k)){if(ch[k][j]=='A'){flag1=1;}if(ch[k][j]=='G'){flag2=1;}if(ch[k][j]=='C'){flag3=1;}if(ch[k][j]=='T'){flag4=1;}}}if(flag1+flag2+flag3+flag4>1){ok=false;}else if(flag1+flag2+flag3+flag4==0){cnt--;}}if(!ok){ans[i]=0;}else{ans[i]=1;for(int j=1;j<=cnt;j++){ans[i]/=4;}}if(i){double cmd=-1;for(int j=0;j<l_len;j++){if(i&(1<<j)){cmd*=-1;}}p1+=ans[i]*cmd;}}for(int i=0;i<(1<<r_len);i++){int cnt=0;bool ok=true;for(int j=1;j<=n;j++){cnt++;int flag1=0,flag2=0,flag3=0,flag4=0;for(int k=0;k<r_len;k++){if(i&(1<<k)){if(ch[k+mid][j]=='A'){flag1=1;}if(ch[k+mid][j]=='G'){flag2=1;}if(ch[k+mid][j]=='C'){flag3=1;}if(ch[k+mid][j]=='T'){flag4=1;}}}if(flag1+flag2+flag3+flag4>1){ok=false;}else if(flag1+flag2+flag3+flag4==0){cnt--;}}if(!ok){ans[i]=0;}else{ans[i]=1;for(int j=1;j<=cnt;j++){ans[i]/=4;}}if(i){double cmd=-1;for(int j=0;j<r_len;j++){if(i&(1<<j)){cmd*=-1;}}p2+=ans[i]*cmd;}}for(int i=1;i<=1000000;i++){for(int j=1;j<=n;j++){tmp[j]="AGCT"[rnd()%4];}bool flag1=false,flag2=false;for(int j=0;j<m;j++){bool flag=true;for(int k=1;k<=n;k++){if(ch[j][k]!='?' && ch[j][k]!=tmp[k]){flag=false;}}if(flag){if(j<mid){flag1=true;}else{flag2=true;}}}if(flag1 && flag2){p3+=0.000001;}}cout<<p1+p2-p3;return 0;
}