【HDU4336】Card Collector-Min-Max容斥

做法：本题需要用到Min-Max容斥。
很久之前我写过这题的状压DP写法，那个做法时间复杂度为)，而今天本人学会了一种新的做法：Min-Max容斥，这个做法比状压DP更加优美一些。
Min-Max容斥，又称最值反演，是指下面这个式子：
}
其中S的最大元素和最小元素。先别急着质问这个式子有什么卵用，我们先看看这个式子是怎么来的。
尝试证明右边等于左边。令}。
说了这么多，这个式子在这题中有什么用呢？Min-Max容斥有一个非常重要的推论：
]
其中S中所有元素都被取过所需的期望时间。我们发现这个时间就相当于取的次数，所以也就是期望次数。
这个推论在这题中就非常有用了，因为本题中)），可以说是比状压DP优美很多了。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
int n;
double p[25],ans;

void solve(int step,int cnt,double totp)
{
    if (step>n)
    {
        if (!cnt) return;
        double f=(cnt%2)?1.0:-1.0;
        ans+=f/totp;
        return;
    }
    solve(step+1,cnt,totp);
    solve(step+1,cnt+1,totp+p[step]);
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%lf",&p[i]);
        ans=0.0;
        solve(1,0,0.0);
        printf("%.6lf
",ans);
    }

    return 0;
}