Endless Spin
给你一段长度为[1..n]的白色区间，每次随机的取一个子区间将这个区间涂黑，问整个区间被涂黑时需要的期望次数。
n<=50
题解
显然是min-max容斥，但是n的范围太大，不能暴力枚举。
设计DP，令f(i,j,k)表示前i个球中必须选第i个球，有j种区间可以选择并且选择他们不会涂黑决定要涂黑的球，决定要涂黑的球的个数是奇数还是偶数的方案数。
转移就考虑第i个球必须选时，上一个决定要选的球是哪个就行了。
注意这题需要实现一个高精度。
CO int N=51;
LL dp[N][N*N][2];
LL ans[100];
IN int sec(int n){
return n*(n+1)/2;
}
void add(LL a,LL b){
ans[0]+=floor((LD)a/b),a-=floor((LD)a/b)*b;
for(int i=1;i<100;++i)
a*=10,ans[i]+=a/b,a%=b;
}
void real_main(){
int n=read<int>();
memset(dp,0,sizeof dp),dp[0][0][0]=1;
for(int i=1;i<=n;++i)for(int j=0;j<=sec(i);++j)
for(int k=i-1;k>=0;--k){ // last ball
if(sec(i-k-1)>j) break;
dp[i][j][0]+=dp[k][j-sec(i-k-1)][1];
dp[i][j][1]+=dp[k][j-sec(i-k-1)][0];
}
memset(ans,0,sizeof ans);
for(int i=1;i<=n;++i)for(int j=0;j<sec(i);++j)
add((dp[i][j][1]-dp[i][j][0])*sec(n),sec(n)-j-sec(n-i));
for(int i=99;i>=16;--i)
if(ans[i]>=10) ans[i-1]+=ans[i]/10,ans[i]%=10;
if(ans[16]>=5) ++ans[15];
for(int i=15;i>=1;--i)
if(ans[i]>=10) ans[i-1]+=ans[i]/10,ans[i]%=10;
printf("%lld.",ans[0]);
for(int i=1;i<=15;++i) printf("%lld",ans[i]);
puts("");
}
int main(){
// freopen("HDU4624.in","r",stdin),freopen("HDU4624.out","w",stdout);
for(int T=read<int>();T--;) real_main();
return 0;
}
按位或
题目描述
刚开始你有一个数字0，每一秒钟你会随机选择一个[0,2^n-1]的数字，与你手上的数字进行或（c++,c的|,pascal的or）操作。选择数字i的概率是p[i]。保证0<=p[i]<=1，Σp[i]=1问期望多少秒后，你手上的数字变成2^n-1。
输入格式
第一行输入n表示n个元素，第二行输入2^n个数，第i个数表示选到i-1的概率
输出格式
仅输出一个数表示答案，绝对误差或相对误差不超过1e-6即可算通过。如果无解则要输出INF
输入输出样例
2 0.25 0.25 0.25 0.25
2.6666666667
说明/提示
对于100%的数据，n<=20
shadowice1984的题解
min-max容斥原理
min-max容斥原理，其实就是两个很简单的等式
记(max(S))为集合S中的最大值，(min(S))为集合S中的最小值，(|S|)为集合(S)的元素数量，那么以下两个等式成立
所谓的min-max容斥原理大概就是这两个简单的等式了，它真正暴力的地方在于我们就算根本没法进行大小比较，也可以仅通过加减法把max或者min以极其暴力的方式(O(2^n))的枚举子集容斥出来
下面我们尝试着给出证明，这里只证明第一个等式好了，后边的可以自行推出
其实只需要证明一件事，就是除了(min(T)=max(S))的那个值，其他的(min)值都被消掉了就可以了(这里说明一下，我们假定集合中的元素两两相异，如果存在相同的值的话，我们给其中几个加上一些eps扰动一下即可，反正不影响最值就是了)
先来说明(max(S))的系数为什么是(1)，假设中S最大的元素是(a)，那么我们会发现只有(min({a})=max(S))所以(max(S))的系数必须是(1)
然后再说明为什么别的(min)都被消掉了，假设某个元素(b)的排名是(k)，那么(min(T)=b)当且仅当我们选出的集合是后(n-k)个的元素构成的集合的子集然后并上({b})得到的，我们会发现显然这样的集合有(2^{n-k})种，而显然这其中恰有(2^{n-k-1})中是有奇数个元素的，恰有(2^{n-k-1})种是有偶数个元素的，两两相消自然就成(0)了。当然上述等式在(k=n)的时候不成立，但是此时剩下的刚好是最大值，所以证明完毕。
一些推导
现在我们有了非常暴力的min-max定理了，让我们来看看我们可以干一些什么事
一个令人惊讶的事实是，min-max定理在期望下成立，我们记(E(max(S)))为集合中(max)值的期望，那么有
那么如何定义在这道题里面的期望呢？
我们现在发现如果认为某个位置变为(1)的步数是一个随机变量的话，那么(E(max(S)))可以认为是某个集合(S)中最晚元素出现的期望时间。（因为最晚的位置都变成(1)了，所有的位置自然都变成(1)了）
那么很现实的一个事情是，我们没法比较两个位置变成(1)的期望步数长短，所以我们要使用min-max容斥原理在没有办法比较大小的情况下的求出(max)来
但是我们必须有一个求出(min)的方式……否则min-max容斥就是白搭，也就是说我们需要求(E(min(T)))，即集合T中最早元素出现的期望时间。
离散随机变量的几何分布
几何分布就是这里有一个离散型随机变量(X),满足
其中(p)是一个常量
然后我们就说这个离散型随机变量(X)服从带参数(p)的几何分布
然后不如让我来试着求一下一个服从几何分布的随机变量的期望？
然后我们发现这大概是一个等比数列*等差数列的数列求和的式子
可以算出来是这个式子
另一些推导
接着上一次推导，我们现在要求(E(min(T)))了
那么我们可以发现(P(min(T)=k))的意义就是前(k-1)次都没有选中这个集合中的哪怕一个数，换句话来讲，前(k-1)次都是选了这个集合补集的子集，然后第(k)次没有选这个集合补集的子集，可以列出这样一个式子,我们记(P(S))为选中(S)子集的概率之和
这是什么？我们发现(min(T))服从系数为(1-P(complement_{U}T))的几何分布！
然后期望直接套公式计算就行啦！
怎么求(P(T))呢？使用快速莫比乌斯变换(FMT)即可。
时间复杂度(O(2^nn))。
#include<bits/stdc++.h>
#define co const
using namespace std;
co double eps=1e-10;
co int N=1<<20;
int n,up,cnt[N];
double p[N];
int main(){
scanf("%d",&n),up=(1<<n);
for(int i=0;i<up;++i) scanf("%lf",p+i),cnt[i]=cnt[i>>1]+(i&1);
for(int k=0;k<n;++k)
for(int s=(up-1)^(1<<k),i=s;;i=(i-1)&s){
p[i|(1<<k)]+=p[i];
if(i==0) break;
}
double ans=0;
for(int i=1;i<up;++i){
if(1-p[(up-1)^i]<eps) return puts("INF"),0;
double e=1/(1-p[(up-1)^i]);
if(cnt[i]&1) ans+=e;
else ans-=e;
}
printf("%lf
",ans);
return 0;
}