Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5272 Accepted Submission(s): 2688
Special Judge
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #include<cstdio> 5 #include<stack> 6 #include<set> 7 #include<map> 8 #include<cmath> 9 #include<ctime> 10 #include<time.h> 11 #include<algorithm> 12 using namespace std; 13 #define mp make_pair 14 #define pb push_back 15 #define debug puts("debug") 16 #define LL long long 17 #define pii pair<int,int> 18 #define eps 1e-10 19 #define inf 0x3f3f3f3f 20 21 double f[(1<<21)+30]; 22 double p[25]; 23 int main() 24 { 25 int t,i,j,k,n,m,u,v; 26 while(scanf("%d",&n)==1){double none=0; 27 for(i=0;i<n;++i) scanf("%lf",p+i),none+=p[i]; 28 int all=(1<<n)-1; 29 memset(f,0,sizeof(f)); 30 for(i=all-1;i>=0;--i){ 31 double Pj=(double)1.00-none,s=0; 32 for(j=0;j<n;++j){ 33 if(i&(1<<j)){ 34 Pj+=p[j]; 35 } 36 else{ 37 s+=p[j]*f[i|(1<<j)]; 38 } 39 } 40 s+=1.00; 41 Pj=1.00-Pj; 42 f[i]=s/Pj; 43 } 44 printf("%.5f\n",f[0]); 45 } 46 return 0; 47 }
容斥做法的话不是很懂说一下简单思路。
E(至少得到i号卡)=1/pi,把他记作E(i),这个的含义就是一直买卡直至第一次出现i卡时停止的期望购买次数,这个式子是可以推出来的,数学不好真tm烦= =E(至少得到A卡或者B卡的)=E(A|B).
我们要求的就是E(至少得到1&2&...&N号卡),不妨记作E(1&2&...&N)=E(1)+E(2)+...+E(n)-{E(1|2)+E(2|3)+......}+{E(1|2|3)+...}.....
就这样一直利用容斥定理奇加偶减算出最终的答案。
以后会了可能会补。
原文:https://www.cnblogs.com/zzqc/p/9025776.html