hdu 5985 Lucky Coins (機率)

好有趣的一個題，真是讓人進一步了解的機率問題，如果太小選擇忽略，這個題目中很簡單就能找到小的那個，0.5的30次方在double中已經為0了，為了保險起見可以選擇100.

令兩個函數 f[i][k] 表示第i種硬币第K步雷射的機率，是以 f[i][k]=(1−pki)ni

revf[i][k] 表示第i種硬币第k步至少有一個活着是以 revf[i][k]=1−f[i][k]

ans[i]=∑k=1100∑j=1,j!=in(rev[i][k]−rev[i][k+1])∗f[j][k−1]

答案看起來很簡單，但是想的是一個個算，然後沒辦法算，沒想怎麼去反着搞。。。

#include <bits\stdc++.h>
using namespace std;
double f[20][120],s[20][160],p[20],ans[20];
int a[20];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%lf",&a[i],&p[i]);
        if(n==1){cout<<1.000000<<endl;continue;}
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=99;j++)
        {
            double temp=pow(p[i],j);
            temp=pow(1-temp,a[i]);
            f[i][j]=temp;
            s[i][j]=1-temp;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans[i]=0;
        for(int j=1;j<99;j++)
        {
            double temp=1;
            for(int k=1;k<=n;k++)
            {
                if(i==k)continue;
                temp*=f[k][j];
            }
            ans[i]+=(s[i][j]-s[i][j+1])*temp;
        }
    }
    for(int i=1;i<n;i++)
    {
        printf("%.6f ",ans[i]);
    }
    printf("%.6f\n",ans[n]);
}
    return 0;
}