UVA概率练习[2]

UVa11021 Tribbles

你有K个麻球。一个只会存活一天。在死亡之前，一个麻球有P_i的概率生出i个麻球(i=0,1,…,n-1)。m天后所有麻球都死亡的概率是多少？（包含在第m天前全部死亡的情况）

麻球之间是独立的，只算一个麻球就行了

直接枚举生出几只麻球算概率

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=;

const double eps=1e-;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,k;

double p[N],f[N];

double Pow(double a,int b){

    double re=1.0;

    for(;b;b>>=,a*=a)

        if(b&) re*=a;

    return re;

}

int main(){

    freopen("tribbles.in","r",stdin);

    freopen("tribbles.out","w",stdout);

    int T=read(),cas=;

    while(T--){

        n=read();k=read();m=read();

        for(int i=;i<n;i++) scanf("%lf",&p[i]);

        f[]=p[];

        for(int i=;i<=m;i++){

            f[i]=p[];

            double po=;

            for(int j=;j<n;j++) po*=f[i-],f[i]+=p[j]*po;

        }

        printf("Case #%d: %.7lf\n",++cas,Pow(f[m],k));

    }

}

Uva11427 Expect the Expected

我喜欢玩纸牌接龙。每次我都有p的概率赢，1-p的概率输。游戏程序会统计我获胜盘数的百分比。如果我一直玩下去，这个百分比就会在p*100%左右浮动。但我仍不满足。

这是我的计划。每天，我都会玩纸牌接龙。如果我赢了，我就高高兴兴地去睡觉。如果我输了，我就一直玩下去直到我这天获胜盘数的百分比严格大于p。这时，我就会宣布胜利，然后高高兴兴地去睡觉。你可以看到，每天我都可以宣布自己保持了获胜比例大于p*100%。我打败了数学规律！

如果你感觉这里好像有什么奇怪的东西，那你就对了。我不可能永远这么做，因为我每天玩的游戏盘数有限。我每天至多玩n盘游戏。那么，这个机智的计划在因为这一限制失败前，执行天数的数学期望是多少？值得注意的是，答案至少为1，因为我至少要玩一天才能发现计划失败了。

每天晚上独立，算一天晚上失败的概率

$f[i][j]$表示$i$局赢了$j$局.....

设失败概率$Q=\sum f[n][j]: \frac{j}{n}\le p$

然后加权上天数求期望，列出来发现是无穷级数.......

$Q+2Q(1-Q)+3Q(1-Q)^2....$

然后看白书，成功得到解法

好吧说个靠谱的：用那些数列求和的技巧把系数弄去，然后套公式

$\sum\limits_{i=1}^{\infty}x^{ik}=\frac{1}{1-x^k}$

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=;

const double eps=1e-;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,k;

double p[N],f[N];

double Pow(double a,int b){

    double re=1.0;

    for(;b;b>>=,a*=a)

        if(b&) re*=a;

    return re;

}

int main(){

    freopen("tribbles.in","r",stdin);

    freopen("tribbles.out","w",stdout);

    int T=read(),cas=;

    while(T--){

        n=read();k=read();m=read();

        for(int i=;i<n;i++) scanf("%lf",&p[i]);

        f[]=p[];

        for(int i=;i<=m;i++){

            f[i]=p[];

            double po=;

            for(int j=;j<n;j++) po*=f[i-],f[i]+=p[j]*po;

        }

        printf("Case #%d: %.7lf\n",++cas,Pow(f[m],k));

    }

}

巴特西

UVA概率练习[2]

最新文章

热门文章