XSY 1899 - Lucky Coins

题目 估算 概率论

---

题意

  我们定义某种硬币为 幸运硬币 : 我们有若干个硬币, 同时将所有的硬币抛起来，然后把反面朝上的硬币移去，留下正面朝上的硬币。接着，再把剩下的硬币同时抛起来，再把反面朝上的硬币移去，直到最终剩下一个种类的硬币或者没有硬币剩下。如果最终剩下一个种类的硬币，那么我们就认为那种硬币为幸运硬币。
  现在给定硬币的种类数、每种硬币的个数、每种硬币抛起来后正面朝上的概率，你需要计算每种硬币成为幸运硬币的概率。

  $1\le T\le 10$
  $1\le k\le 10$
  $0.4\le p_i\le 0.6$
  $\sum c\le 10^6$

分析

  记 $Fail(i,p)$ 表示一枚 抛一次朝上概率为 $p$ 的硬币, 在前 $i$ 轮中出现反面朝上的概率, 那么

$$Fail(i,p)=1-p^i$$
  对于当前 $x$ 成为幸运硬币的概率, 我们可以方便地计算答案:
$$ans(x)=\sum_{i=1}^{\infty}(1-Fail(i,x)^{c_x})(\prod_{j\ne x}Fail(i,j)^{c_j}-\prod_{j\ne x}Fail(i-1,j)^{c_j})$$
  发现当 $i$ 比较大时, $1-Fail(i,x)^{c_x}\approx 0$ , 所以我们只用将 $i$ 从 $1$ 枚举到 $T$ , 我取了 $T=80$ .

实现

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define P(i,a,b) for (int i=(a);i>=(b);i--)
#define D double
const int K=15;
int T;
int k,a[K]; D b[K];
int rd(void) {
    int x=0,f=1; char c; for (c=getchar();!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
}
D fail(int turn,D p,int cnt) { return pow( 1-pow(p,(D)turn) ,(D)cnt); }
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("C.in","r",stdin);
        freopen("C.out","w",stdout);
    #endif
    T=rd();
    F(t,1,T) {
        k=rd();
        F(i,1,k) {
            a[i]=rd();
            scanf("%lf",b+i);
        }
        if (k==1) { printf("1.000000000\n"); continue; }
        F(lucky,1,k) {
            D ans=0;
            F(i,1,50) {
                D tmp=1-fail(i,b[lucky],a[lucky]),sum1=1,sum2=1;
                F(j,1,k) if (j!=lucky) {
                    sum1 *= fail(i-1,b[j],a[j]);    //全部在 i-1 前炸
                    sum2 *= fail(  i,b[j],a[j]);    //全部在 i   前炸
                    // sum2 - sum1 : 存在至少一个在 i 炸, 且最晚在 i 炸
                }
                tmp *= (sum2-sum1); ans+=tmp;
            }
            printf("%0.9lf ",ans);
        }
        printf("\n");
    }
    return 0;
}