menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[Min-Max容斥+高维前缀和]BZOJ4036(HAOI2015)【按位或】题解
local_offer 查看标签
comment 0 条评论

题目概述

我写过了来着,鸽了。

解题报告

用Min-Max容斥再做一遍这题,学习自memset0

Min-Max容斥,对于一个集合 $S$ ,他的最大值 $max(S)$ 和子集 $T$ 的最小值 $min(T)$ 的关系如下:

$$ max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T) $$

证明:设 $S$ 中 $a_{x+1}$ 为第 $x+1$ 大的数(有 $x$ 个数比 $a_{x+1}$ 大),则所有 $min(T)=a_{x+1}$ 的集合 $T$ 的总贡献为

$$ a_{x+1}\sum_{i=0}^{x}(-1)^{(i+1)-1}{x\choose i}=a_{x+1}\sum_{i=0}^{x}(-1)^i{x\choose i}=a_{x+1}(1-1)^{x} $$

那么对于所有 $x$ ,总贡献就是:$\sum_{x=0}^{|S|-1}a_{x+1}\cdot0^{x}$ ,只有在 $x=0$ 也就是选了最大值时有贡献,所以原式得证。


2019.1.31UPD:重新填一下构造的坑。

构造容斥系数 $f(i)$ 使得 $max(S)=\sum_{T\subseteq S}f(|T|)min(T)$ ,那么同证明可以得出总贡献:

$$ \sum_{x=0}^{|S|-1}a_{x+1}\sum_{i=0}^{x}f(i+1){x\choose i} $$

因为 $max(S)=a_1$ ,所以 $\sum_{i=0}^{x}f(i+1){x\choose i}=[x=0]​$ ,根据二项式反演

$$ f(x+1)=\sum_{i=0}^{x}(-1)^{x-i}{x\choose i}[i=0]=(-1)^x $$

所以 $f(i)=(-1)^{i-1}$ 即 $max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T)$ 。


这道题对于一个集合 $S$ ,可以令 $max(S)$ 表示 $S$ 集合中最晚出现的元素第一次出现的期望时间,那么对应的 $min(S)$ 就表示 $S$ 集合中最早出现的元素第一次出现的期望时间,可以得到:

$$ max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T)\\ min(T)={1\over\sum_{A\cap T\not=\emptyset}P_A}={1\over 1-\sum_{A\cap T=\emptyset}P_A}={1\over1-\sum_{(U-A)\cap T=T}P_A} $$

所以就可以用高维前缀和求出 $min(T)$ ,然后求出答案 $max(U)$。

ps:发生概率为 $p$ 的事件一直重复,则发生的期望时间为 $1\over p$ ,证明的话考虑错位相减和等比数列求和:

$$ S(k)=p\sum_{i=1}^{k}i(1-p)^{i-1}\\ S(k)-(1-p)S(k)=pS(k)=(p\sum_{i=1}^{k}(1-p)^{i-1})-pk(1-p)^k=1-(pk+1)(1-p)^{k}\\ k\to+\infty,pS(k)=1,S(k)={1\over p} $$

示例程序

#include<cstdio>
using namespace std;
typedef long double DB;
const int maxn=20,maxs=1<<maxn;

int n,S,cnt[maxs];DB f[maxs],ans;

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);S=1<<n;for (int i=0;i<S;i++) {double x;scanf("%lf",&x);f[(~i)&(S-1)]=x;}
    for (int i=0;i<n;i++) for (int j=1<<i;j<S;j=(j+1)|(1<<i)) f[j^(1<<i)]+=f[j];
    for (int i=1;i<S;i++){
        cnt[i]=cnt[i>>1]+(i&1);if (f[i]==1) return puts("INF"),0;
        f[i]=1/(1-f[i]);cnt[i]&1?ans+=f[i]:ans-=f[i];
    }return printf("%.10f\n",(double)ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up