锐客网

  1. 首页 > 睿知 > it技术 > >

[SRM478]RandomApple

randomappleIT知识

高斋晓开卷，独共圣人语。这篇文章主要讲述[SRM478]RandomApple相关的知识，希望能为你提供帮助。
题意：有$k$种苹果和$n$个箱子，每个箱子中有一些苹果，先等概率选取$n$个箱子组成集合的非空子集，再从选出的苹果中随机选一个，问每种苹果被选中的概率是多少
设箱子$i$有$cnt_{i,j}$个第$j$种苹果，第$i$个箱子的总苹果数$siz_i=sumlimits_{j=1}^kcnt_{i,j}$，苹果总数$sum=sumlimits_{i=1}^nsiz_i$
因为选完非空子集后，每个箱子中的苹果被选中的概率是相同的，所以先考虑选箱子，设$f_{i,j}$表示在前$i$个箱子中选$j$个苹果的方案数（只能一箱一箱选），那么$f_{i,j}=f_{i-1,j}+f_{i-1,j-siz_i}$
再设$g_{i,j}$表示在所有不是$i$的箱子中选$j$个苹果的方案数，那么$g_{i,j}=f_{n,j}-g_{i,j-siz_i}$
【[SRM478]RandomApple】于是，选中了箱子$i$的情况对箱子$i$中每个苹果被选中的概率贡献为$frac1{2^n-1}sumlimits_{j=0}^{sum-siz_i}frac{g_{i,j}}{j+siz_i}$（枚举箱子$i$外被选中的苹果数）

#include< stdio.h> #include< vector> #include< string> #include< string.h> using namespace std; typedef double du; typedef long long ll; ll f[500010],g[500010]; int cnt[60][60],siz[60],sum; class RandomApple{ public: vector< du> theProbability(vector< string> hun,vector< string> ten,vector< string> one){ int n,k,i,j; du t; n=hun.size(); k=hun[0].length(); for(i=0; i< n; i++){ for(j=0; j< k; j++){ cnt[i][j]=(hun[i][j]-‘0‘)*100+(ten[i][j]-‘0‘)*10+one[i][j]-‘0‘; siz[i]+=cnt[i][j]; } sum+=siz[i]; } vector< du> res(k,0); f[0]=1; for(i=0; i< n; i++){ for(j=sum; j> =siz[i]; j--)f[j]+=f[j-siz[i]]; } for(i=0; i< n; i++){ memset(g,0,sizeof(g)); t=0; for(j=0; j< =sum; j++){ g[j]=f[j]-(j> =siz[i]?g[j-siz[i]]:0); if(j+siz[i]< =sum)t+=g[j]/(du)((1ll< < n)-1)/(du)(j+siz[i]); } for(j=0; j< k; j++)res[j]+=t*cnt[i][j]; } return res; } }; /* int main(){ RandomApple cl; vector< string> a,b,c; vector< du> res; char s[60]; for(scanf("%s",s); s[0]!=‘-‘; scanf("%s",s))a.push_back(s); for(scanf("%s",s); s[0]!=‘-‘; scanf("%s",s))b.push_back(s); for(scanf("%s",s); s[0]!=‘-‘; scanf("%s",s))c.push_back(s); res=cl.theProbability(a,b,c); for(du t:res)printf("%.9lf ",t); } */


    推荐阅读


    上一篇：Android app ADB命令

    下一篇：投稿|内外交困，电商代运营告别「躺赚年代」