做技术一般逛那些网站,网站建设报价模块,亚马逊电商运营新手入门,做公司员工福利的网站都有哪些Lucky Conins
题意
最多共101010种硬币,所有的硬币之和不超过100000100000100000,每次将所有的硬币抛出,第iii中硬币正面朝上的概率为pip_ipi,将反面朝上的硬币移除掉.直至最后剩一种硬币或没有硬币则停止.若最后剩余一种硬币,则称这种硬币是幸运的,求每种硬币的幸运概率. …Lucky Conins
题意
最多共101010种硬币,所有的硬币之和不超过100000100000100000,每次将所有的硬币抛出,第iii中硬币正面朝上的概率为pip_ipi,将反面朝上的硬币移除掉.直至最后剩一种硬币或没有硬币则停止.若最后剩余一种硬币,则称这种硬币是幸运的,求每种硬币的幸运概率.
题解
推公式题.
假设我们要求第iii种硬币成为幸运硬币的概率,那么我们可以求其在第xxx步成为幸运硬币的概率,然后对xxx求和即可.
计算硬币iii在xxx步成为幸运硬币的概率:
一.第iii种硬币,必须在第xxx步至少剩111个:
[1] : Alive[i,x]1−(1−pix)ciAlive[i,x] 1-(1-p_i^x)^{c_i}Alive[i,x]1−(1−pix)ci 硬币iii在第xxx步存活:pixp_i^xpix,在第xxx步及之前死亡:1−pix1-p_i^x1−pix,第iii种所有硬币在第xxx步都死亡(1−pix)ci(1-p_i^x)^{c_i}(1−pix)ci,第iii种在第xxx步至少剩余一个硬币1−(1−pix)ci1-(1-p_i^x)^{c_i}1−(1−pix)ci 二. 第jjj种硬币,至少有一枚要在第x−1x-1x−1步存活,第xxx步死亡
先考虑对于第jjj种硬币,它至少有一枚硬币第x−1x-1x−1步存活,在第xxx步死亡的概率.
假设第jjj种有ttt枚硬币在第x−1x-1x−1步存活,在第xxx步死亡:
Ccjt(pjx−1)t(1−pjx−1)cj−t(1−pj)tCcjt(pjx−1−pjx)t(1−pjx−1)cj−tC_{c_j}^t(p_j^{x-1})^t(1-p_j^{x-1})^{c_j-t}(1-p_j)^t C_{c_j}^t(p_j^{x-1}-p_j^{x})^t(1-p_j^{x-1})^{c_j-t}Ccjt(pjx−1)t(1−pjx−1)cj−t(1−pj)tCcjt(pjx−1−pjx)t(1−pjx−1)cj−t
对ttt从111到cjc_jcj求和,利用二项式定理我们得到了第jjj种硬币,它至少有一枚硬币第x−1x-1x−1步存活,在第xxx步死亡的概率:
[2] : (1−pjx)cj−(1−pjx−1)cj(1-p_j^{x})^{c_j}-(1-p_j^{x-1})^{c_j}(1−pjx)cj−(1−pjx−1)cj.
三.除第iii种之外的所有硬币,至少有111枚在x−1x-1x−1步存活,在第xxx步死亡
为避免重复计算
设jjj是不与iii相等的数中最小的. 我们考虑是第jjj种硬币起到了这个作用,那么jjj种以后的硬币只要满足在xxx步及之前死光即可.
然后再考虑是jtjtjt种硬币起到了这个作用,那么jtjtjt种以后的硬币只要满足在xxx步及之前死光即可,并且要满足第jtjtjt种之前的硬币必须不能起作用(即在x−1x-1x−1步及之前就必须全部死光),否则会算重.
也就是说我们需要记录lft[j,x]lft[j,x]lft[j,x]表示jjj种之前的硬币全部在第x−1x-1x−1步及之前就死光.记录rgt[j,x]rgt[j,x]rgt[j,x]表示jjj种之后的硬币全都在第xxx步及之前就死光. 其中lft[j,x]∑t≠i,tlt;j(1−ptx−1)ctlft[j,x] \sum_{t \ne i,t lt; j}(1-p_t^{x-1})^{c_t}lft[j,x]∑t̸i,tj(1−ptx−1)ct,rgt[j,x]∑t≠i,tgt;jn(1−ptx)ctrgt[j,x] \sum_{t\ne i,t gt; j}^n(1-p_t^x)^{c_t}rgt[j,x]∑t̸i,tjn(1−ptx)ct 那么这部分的答案就是
∑j≠i((1−pjx1)cj−(1−pjx)cj)∗lft[j,x]∗rgt[j,x]\sum_{j \ne i}((1-p_j^{x1})^{c_j}-(1-p_j^x)^{c_j})*lft[j,x]*rgt[j,x]∑j̸i((1−pjx1)cj−(1−pjx)cj)∗lft[j,x]∗rgt[j,x]
四.最终公式
(1−(1−pix)ci)∑j≠i(((1−pjx)cj−(1−pjx−1)cj)∗lft[j,x]∗rgt[j,x])(1-(1-p_i^x)^{c_i})\sum_{j \ne i}(((1-p_j^{x})^{c_j}-(1-p_j^{x-1})^{c_j})*lft[j,x]*rgt[j,x])(1−(1−pix)ci)∑j̸i(((1−pjx)cj−(1−pjx−1)cj)∗lft[j,x]∗rgt[j,x])
代码
#include iostream
#include algorithm
#include cstring
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)double p[11];
int cnt[11];
int n;
const int lim 50;
double fastpow(double x,int n) {double res 1.0;while(n) {if(n1) res * x;x * x;n 1; }return res;
} double f(int id,int x) {return fastpow(1-fastpow(p[id],x),cnt[id]) - fastpow(1-fastpow(p[id],x-1),cnt[id]);
}double calc(int i) {double ans 0;rep(x,1,lim) {double res 1-fastpow(1-fastpow(p[i],x),cnt[i]);double tmp 0,lft 1;rep(j,1,n) {if(j i) continue;double rgt 1;rep(t,j1,n) {if(i t) continue;rgt * fastpow(1-fastpow(p[t],x),cnt[t]);}tmp f(j,x)*lft*rgt;lft * fastpow(1-fastpow(p[j],x-1),cnt[j]);}ans res * tmp;}return ans;
}
int main() {int T;std::cin T;while(T--) {std::cin n;rep(i,1,n) {std::cin cnt[i] p[i];}if(n 1) {printf(%.6f\n,1.0);continue;}rep(i,1,n) {if(i ! 1) printf( );printf(%.6f,calc(i));}puts();}return 0;
}
