我方有 \(n\) 个小黄人，分别为 \(a_i\), 敌方有 \(m\) 个小黄人，分别为\(b_i\), 小黄人的健康值为 \([1,6]\) 中的整数 .
有 \(d\) 个炸弹，每次会有均匀的概率摧毁我方和敌方的任何活着的小黄人，此时这个被选中的小黄人健康值 --，如果健康值为0的话，小黄人就会死掉。
\(d\) 个炸弹之后，敌方小黄人全死光的概率是多少（我方小黄人是不是活着不重要）。
\(1\leq n,m\leq 5, 1\leq d\leq 100\)
简单的想法，用一共 \(n+m\) 个范围为 \(0\) 到 \(6\) 的位置来表示当前每个小黄人的健康值，然后还需要一个维表示有多少个 bombs 剩下。
但这个时间复杂度肯定是爆炸的，此时观察到是否是敌方/我方小黄人是重要的，但是敌方 & 我方小黄人中每个位置上当前健康值是多少是不重要的。只需要知道我方/敌方当前有多少个小黄人健康值为 \(0,1,2,3,4,5,6\) 就好了。
此时就可以状态为 \((s_0, s_1, s_2,s_3,s_4,s_5,s_6)\) ，这个大概在不到 \(500\) 个.
这里需要注意是需要状压的，实际出现的可能组合远远小于 \(7^5\) .
假设当前状态为 \(f(i,s_0,s_1,s_2,s_3,s_4,s_5,s_6,t_0,t_1,t_2,t_3,t_4,t_5,t_6)\),
此时炸到健康值为 \(s_i, i>0\) 的概率是 \(\frac{s_i}{\sum{s_j}+\sum{t_j}-s_0-t_0}\),
只需要把 \(f(i,s_0,s_1,s_2,s_3,s_4,s_5,s_6,t_0,t_1,t_2,t_3,t_4,t_5,t_6) \times \frac{s_i}{\sum{s_j}+\sum{t_j}-s_0-t_0}\) 转移到新的 \(f(i-1,\cdots,s_{i-1}+1,s_i-1,\cdots,t_0,t_1,t_2,t_3,t_4,t_5,t_6)\) 就可以啦。
对于选择的是 \(t_i\) 的同理。
时间复杂度: \(O(500^2d)\)
空间复杂度: \(O(500^2d)\)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int D=505;
const double eps=1e-18;
int n,m,d;
int a[10],b[10],sta[D],stb[D],cnta[10],cntb[10],tota=0,totb=0;
map<int,int>ma,mb;
inline int calc(int s0,int s1,int s2,int s3,int s4,int s5,int s6){int mask=s6;mask=mask*6+s5;mask=mask*6+s4;mask=mask*6+s3;mask=mask*6+s2;mask=mask*6+s1;mask=mask*6+s0;return mask;
}
void dfsa(int s0,int s1,int s2,int s3,int s4,int s5,int s6,int tot){if(s0+s1+s2+s3+s4+s5+s6==tot){if(ma.find(calc(s0,s1,s2,s3,s4,s5,s6))==ma.end()){sta[tota]=calc(s0,s1,s2,s3,s4,s5,s6);ma[calc(s0,s1,s2,s3,s4,s5,s6)]=tota++;}return;}dfsa(s0+1,s1,s2,s3,s4,s5,s6,tot);dfsa(s0,s1+1,s2,s3,s4,s5,s6,tot);dfsa(s0,s1,s2+1,s3,s4,s5,s6,tot);dfsa(s0,s1,s2,s3+1,s4,s5,s6,tot);dfsa(s0,s1,s2,s3,s4+1,s5,s6,tot);dfsa(s0,s1,s2,s3,s4,s5+1,s6,tot);dfsa(s0,s1,s2,s3,s4,s5,s6+1,tot);
}
void dfsb(int s0,int s1,int s2,int s3,int s4,int s5,int s6,int tot){if(s0+s1+s2+s3+s4+s5+s6==tot){if(mb.find(calc(s0,s1,s2,s3,s4,s5,s6))==mb.end()){stb[totb]=calc(s0,s1,s2,s3,s4,s5,s6);mb[calc(s0,s1,s2,s3,s4,s5,s6)]=totb++;}return;}dfsb(s0+1,s1,s2,s3,s4,s5,s6,tot);dfsb(s0,s1+1,s2,s3,s4,s5,s6,tot);dfsb(s0,s1,s2+1,s3,s4,s5,s6,tot);dfsb(s0,s1,s2,s3+1,s4,s5,s6,tot);dfsb(s0,s1,s2,s3,s4+1,s5,s6,tot);dfsb(s0,s1,s2,s3,s4,s5+1,s6,tot);dfsb(s0,s1,s2,s3,s4,s5,s6+1,tot);
}
double f[D][D][D];
void solv(int lft,int ida,int idb){int maska=sta[ida],maskb=stb[idb];for(int i=0;i<=6;i++)cnta[i]=maska%6,maska/=6;for(int i=0;i<=6;i++)cntb[i]=maskb%6,maskb/=6;int ala=0,alb=0;for(int i=1;i<=6;i++)ala+=cnta[i];for(int i=1;i<=6;i++)alb+=cntb[i]; for(int i=1;i<=6;i++)if(cnta[i]){cnta[i]--;cnta[i-1]++;int nmska=calc(cnta[0],cnta[1],cnta[2],cnta[3],cnta[4],cnta[5],cnta[6]);int nida=ma[nmska];cnta[i]++;cnta[i-1]--;f[lft+1][nida][idb]+=f[lft][ida][idb]/(ala+alb)*cnta[i];}for(int i=1;i<=6;i++)if(cntb[i]){cntb[i]--;cntb[i-1]++;int nmskb=calc(cntb[0],cntb[1],cntb[2],cntb[3],cntb[4],cntb[5],cntb[6]);int nidb=mb[nmskb];cntb[i]++;cntb[i-1]--;f[lft+1][ida][nidb]+=f[lft][ida][idb]/(ala+alb)*cntb[i];}if(ala+alb==0){f[lft+1][ida][idb]+=f[lft][ida][idb];}
}
void get_ans(double&ans,int ida,int idb){int maska=sta[ida],maskb=stb[idb];for(int i=0;i<=6;i++)cnta[i]=maska%6,maska/=6;for(int i=0;i<=6;i++)cntb[i]=maskb%6,maskb/=6;if(cntb[0]==m)ans+=f[d][ida][idb];
}
int main(){cin>>n>>m>>d;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>b[i];dfsa(0,0,0,0,0,0,0,n);dfsb(0,0,0,0,0,0,0,m);
// cerr<<tota<<endl;
// for(int i=0;i<tota;i++)cerr<<sta[i]<<" ";cerr<<endl;
// cerr<<totb<<endl;
// for(int i=0;i<totb;i++)cerr<<stb[i]<<" ";cerr<<endl; for(int i=1;i<=n;i++)cnta[a[i]]++;for(int i=1;i<=m;i++)cntb[b[i]]++;int omska=calc(cnta[0],cnta[1],cnta[2],cnta[3],cnta[4],cnta[5],cnta[6]);int omskb=calc(cntb[0],cntb[1],cntb[2],cntb[3],cntb[4],cntb[5],cntb[6]);f[0][ma[omska]][mb[omskb]]=1.0;for(int i=0;i<d;i++){for(int ida=0;ida<tota;ida++)for(int idb=0;idb<totb;idb++){if(f[i][ida][idb]<eps)continue;solv(i,ida,idb);}}double ans=0;for(int ida=0;ida<tota;ida++)for(int idb=0;idb<totb;idb++){get_ans(ans,ida,idb);}cout<<fixed<<setprecision(8)<<ans<<endl;return 0;
}
/*
5 5 100
6 6 6 6 6
6 6 6 6 6
*/
/*
1 1 12
6
6
*/