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

标签: none

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu