Cptraser/ 三月 11, 2019/ 2019.3/ 0 comments

先给式子:

    \[max(S)=\sum_{T\in S}(-1)^{|T|-1}min(T)\]

由于min-max容斥对于期望同样满足,所以可以很方便地解决一些概率和期望问题。

在期望里也适用:

    \[E(max(S))=\sum_{T\in S}(-1)^{|T|-1}E(min(T))\]

(以上minmax都可以互换)

HDU4336 Card Collector

题目大意:有n种卡片,每一秒都有P_i的概率获得一张第i种卡片,求每张卡片都至少有一张的期望时间。

max(S)表示获得最后一张卡片的期望时间,min(S)表示获得第一张的期望时间。

同样满足:

    \[max(S)=\sum_{T\in S}(-1)^{|T|-1}min(T)\]

同时此题:

    \[min(T)=\frac{1}{\sum_{i\in T}P_i}\]

dfs即可。

#include <cstdio>
using namespace std;

double P[25],Ans;
int N;

void dfs(int x,int t,double tot){
    if(x==N+1){
        if(t)Ans+=(double)((t-1)&1?-1:1)*(1.0/tot);
        return ;
    }
    dfs(x+1,t+1,tot+P[x]);
    dfs(x+1,t,tot);
}

int main()
{
    while(~scanf("%d",&N)){Ans=0;
        for(int i=1;i<=N;i++)scanf("%lf",&P[i]);
        dfs(1,0,0);printf("%lf\n",Ans);
    }
}

BZOJ4036按位或

max(S)表示最后一位被或到的期望时间,min(S)表示第一个被或到的期望时间。

    \[min(T)=\frac{1}{\sum_{S^{'}\bigcap T\neq\varnothing}P_i}\]

    \[\sum_{S^{'}\bigcap T\neq\varnothing}P_i=(1-\sum_{S^{'}\bigcap T=\varnothing}P_i)\]

等式右边的东西其实就是T的补集。

所以只要求(求答案时带入补集即可):

    \[\sum_{S^{'}\in T}P_i(i\in S^{'})\]

转化为FWT

    \[f[i]=\sum_{j|i=i}P_j\]

#include <cstdio>
using namespace std;


int N,M,Cnt[1<<20|10];
double F[1<<20|10],P[1<<20|10];
void FMT(void){
    for(int i=0;i<(1<<N);i++)F[i]=P[i];
    for(int i=0;i<N;i++)
        for(int j=0;j<(1<<N);j++)if((j>>i)&1){
            F[j]+=F[j^(1<<i)];
        }
}

bool Check(void){int tot=0;
    for(int i=0;i<(1<<N);i++)if(P[i]>0)tot|=i;
    return tot==((1<<N)-1);
}
void Solve(void){
    double Ans=0;
    for(int i=1;i<(1<<N);i++){
        Ans+=(double)(Cnt[i]&1?1:-1)*(1.0/(1.0-F[(1<<N)-1-i]));
    }printf("%lf\n",Ans);
}

int main()
{
    scanf("%d",&N);
    for(int i=0;i<(1<<N);i++)scanf("%lf",&P[i]);
    for(int i=1;i<(1<<N);i++)Cnt[i]=Cnt[i>>1]+(i&1);
    if(!Check())return puts("INF"),0;
    return FMT(),Solve(),0;
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*