http://acm.fzu.edu.cn/problem.php?pid=2103
Problem DescriptionBin has a dream that he and Jing are both in a wonderland full of beautiful gifts. Bin wants to choose some gifts for Jing to get in her good graces.
There are N different gifts in the wonderland, with ID from 1 to N, and all kinds of these gifts have infinite duplicates. Each time, Bin shouts loudly, “I love Jing”, and then the wonderland random drop a gift in front of Bin. The dropping probability for gift i (1≤i≤N) is P(i). Of cause, P(1)+P(2)+…+P(N)=1. Bin finds that the gifts with the higher ID are better. Bin shouts k times and selects r best gifts finally.
That is, firstly Bin gets k gifts, then sorts all these gifts according to their ID, and picks up the largest r gifts at last. Now, if given the final list of the r largest gifts, can you help Bin find out the probability of the list?
InputThe first line of the input contains an integer T (T≤2,000), indicating number of test cases.
For each test cast, the first line contains 3 integers N, k and r (1≤N≤20, 1≤k≤52, 1≤r≤min(k,25)) as the description above. In the second line, there are N positive float numbers indicates the probability of each gift. There are at most 3 digits after the decimal point. The third line has r integers ranging from 1 to N indicates the finally list of the r best gifts’ ID.
Output Sample Input Sample Output Source#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXN 200
#define ll long long
/*ll C(ll n, ll k)
{
ll m=1,t=1;
for(ll i=2;i<=n-k;i++)
m*=i;
for(ll i=k+1;i<=n;i++)
t*=i;
return t/m;
}*/
long long C(ll n,ll k)
{
ll i;
long long ans=1;
for ( i = 1; i <=k ; i++)
{
ans*= (n-i+1);
ans/=i;
}
return ans;
}
double Pow(double a,ll n)
{
double ans = 1;
for(ll i=0;i<n;i++)
{
ans*=a;
}
return ans;
}
int main()
{
//freopen("B.txt","r",stdin);
ll ncase,n,k,r,tmp,tt,mmin,ttt,rr;
double p[MAXN],ans,tmpans,restp,restnum;
ll li[MAXN],num[MAXN],cnt[MAXN];
cin>>ncase;
while(ncase--)
{
memset(num,0,sizeof(num));
ans=1;
tmp=1;
tmpans=restp=restnum=rr=0;
mmin=MAXN;
cin>>n>>k>>r;
for(ll i=1;i<=n;i++)
{
scanf("%lf",&p[i]);
}
for(ll i=1;i<=r;i++)
{
cin>>li[i];
num[li[i]]++;
mmin=min(mmin,li[i]);
}
tt=k;
for(ll i=1;i<=n;i++)
{
if(num[i]&&i!=mmin)
{
tmp=C(tt,num[i]);
ans*=tmp*Pow(p[i],num[i]);
tt-=num[i];
}
}
restnum=tt;
//tt=num[mmin];
for(ll i=1;i<mmin;i++)
{
restp+=p[i];
}
for(ll i=num[mmin];i<=restnum;i++)
{
tmpans+=C(restnum-i,restnum-i)*Pow(restp,restnum-i)*C(restnum,i)*Pow(p[mmin],i);
}
ans*=tmpans;
printf("%.6lf\n",ans);
}
return 0;
}
概率题 fzu Problem 2103,布布扣,bubuko.com
原文：http://blog.csdn.net/u011026968/article/details/23692533