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;
}