min-max容斥
给定集合,设为中的最大值,为中的最小值,则我们有一个式子:
这个东西就叫做min-max容斥。
怎么证明?
我们考虑构造一个容斥系数,使得
考虑第大的元素会被统计到的贡献。
则这个贡献为
简单来说,就是枚举有哪些集合的最小值会为第大的元素。
则
二项式反演一下
得到
因此
综上,
证明完毕。
下面我们来看几道例题。
由于min-max容斥对于期望同样满足,所以可以很方便地解决一些概率和期望问题。
hdu4336 Card Collector
有n种卡片,每一秒都有的概率获得一张第种卡片,求每张卡片都至少有一张的期望时间。
我们记为中最后获得的那种卡片第一次获得的期望时间,为中的第一个获得的那种卡片第一次获得的期望时间。
仍然满足
而
直接计算即可。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=25;
const double eps=1e-7;
double a[N],ans;
int n;
void dfs(int now,int tot,double sum){
if(now>n){
if(sum>eps){
if(tot&1){
ans+=1/sum;
}else{
ans-=1/sum;
}
}
return;
}
dfs(now+1,tot,sum);
dfs(now+1,tot+1,sum+a[now]);
}
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
scanf("%lf",&a[i]);
}
ans=0;
dfs(1,0,0);
printf("%lf
",ans);
}
return 0;
}
bzoj4036 按位或
我们记为中最后被或到的元素第一次被或到的期望时间,为中的第一个被或到的元素第一次被或到的期望时间。
而
我们如果求出了,就直接计算就好了。
怎么求?
然后计算即可。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1050005;
int n,all,tmp,cnt[N];
double sum,res,ans,a[N];
int main(){
scanf("%d",&n);
all=1<<n;
for(int i=0;i<all;i++){
cnt[i]=cnt[i>>1]+(i&1);
scanf("%lf",&a[i]);
sum+=a[i];
if(fabs(a[i])>1e-6){
tmp|=i;
}
}
if(tmp!=all-1){
puts("INF");
return 0;
}
for(int i=1;i<all;i<<=1){
for(register int j=0;j<all;j+=(i<<1)){
for(register int k=j;k<j+i;k++){
a[k+i]+=a[k];
}
}
}
for(register int i=0;i<all;i++){
res=sum-a[all-1-i];
if(res>1e-6){
res=1/res;
}else{
res=0;
}
if(cnt[i]&1){
ans+=res;
}else{
ans-=res;
}
}
printf("%.8lf
",ans);
return 0;
}
推广 kth min-max容斥
我们考虑构造一个容斥系数,使得
考虑第大的元素会被统计到的贡献。
这个贡献为
则
二项式反演一下
得到
因此
综上,
有一道例题,还没弄懂,不会做:重返现世
这道题是ypl学长的神题QwQ