HDU 4624 期望
HDU 4624 期望
一行 $ N $ 个白色的球,每次等概率随机一个区间 $ [L,R] $ 将这些染黑。问期望多少次染黑所有球。
Sol.
@CLJ 的题。计数问题选讲的课件里有。
可知题目所求为 $ \mathbb{E}[\max_{i=1}^nX_i] $ ,其中 $ X_i $ 表示这个位置被染黑的时间,由期望的线性性和 maximum-minimums identity 有
$$ \mathbb E[\max_{i=1}^n X_i]=\sum_{S\sub[n]}(-1)^{|S|-1} \mathbb{E}[\min_{i\in S}X_i] $$
问题变为怎么求 $ \mathbb E[\min_{i\in S} X_i] $ ,这表示第一次染到 $ S $ 这个集合的期望时间,其等于 $ {{n+1\choose2}\over A} $ ,其中 $ A $ 为覆盖 $ S $ 中至少一个点的区间个数。
考虑递推算这个东西。 $ f_{i,s,b} $ 表示考虑前 $ i $ 个白球,黑球(未覆盖)区间数为 $ s $ 且黑球的奇偶性为 $ b $ (容斥用)的的时间,则有
$$ f_{i,s,b}=\sum_{j}f_{j,s-{i-j\choose2},b\oplus1} $$
那么 $ \mathbb{E}[\max_{i=1}^n X_i]={n+1\choose2}\sum_{i}{f_{i,t,1}-f_{i,t,0}\over{n+1\choose2}-t-{n-i+1\choose2}} $ .
原题要高精度小数……懒得写了……
Code
#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
#define G(n) (((n) * (n + 1)) >> 1)
long long f[55][2555][2];
int main()
{
int t; read(t);
while(t--)
{
int n; read(n);
memset(f, 0, sizeof f);
f[0][0][0] = 1;
for(int i = 1; i <= n; ++i) for(int j = 0; j < i; ++j) for(int s = G(i - j - 1); s <= G(i); ++s)
f[i][s][0] += f[j][s - G(i - j - 1)][1], f[i][s][1] += f[j][s - G(i - j - 1)][0];
long double ans = 0, tot = G(n);
for(int i = 1; i <= n; ++i) for(int s = 0; s <= G(i); ++s) if(f[i][s][1] - f[i][s][0] != 0)
ans += tot * (f[i][s][1] - f[i][s][0]) / (tot - s - G(n - i));
printf("%.15Lf\n", ans);
}
return 0;
}