hdu 4336 Card Collector 容斥原理

时间:2021-10-13 17:06:53

读完题目就知道要使用容斥原理做!

下面用的是二进制实现的容斥原理,详见:http://www.cnblogs.com/xin-hua/p/3213050.html

代码如下:

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
double an[];
double solve(int n)
{
int i,j;
double ans=0.0;
for(i=;i<(<<n);i++){
int num=;
double sum=0.0;
for(j=;j<n;j++){
if(i&(<<j)){
num++;
sum+=an[j];
}
}
if(num&) ans+=1.0/sum;
else ans-=1.0/sum;
}
return ans;
}
int main(){
int n,i;
while(cin>>n){
for(i=;i<n;i++)
cin>>an[i];
printf("%lf\n",solve(n));
}
return ;
}