BZOJ 2698: 染色 – [概率与期望]


题目传送门(BZOJ)

题解 :

由于期望满足可加性, 所以我们只需要分别求出覆盖每个点的概率再加和就是答案了
而每个点被覆盖的概率又等于$1-$它不被覆盖的概率
设 $F[i]$ 为覆盖 $i$ 这么长的一段区间的方案数 $F[x]$ 可以简单的递推出来,
而对于点 $i$, 盖不到它的概率就是一次染色盖不到它的概率 $(F[i-1]+F[n-i])/F[n]$ 的 $M$ 次方
写个快速幂, 把每个点被覆盖的概率求出来加和就行了

代码 :

#include <cstdio>
#define f2 double
#define ll long long
inline f2 qp(f2 x, int y) {
    f2 res = 1;
    for(; y; y >>= 1, x *= x) if(y&1) res*=x;
    return res;
}
ll f[1000001];
f2 ans = 0;
int main() {
    int n, m, l, r; scanf("%d%d%d%d", &n, &m, &l, &r);
    for(int i = l; i <= r; i ++ ) f[i] = f[i-1]+i-l+1;
    for(int i = r+1;i<= n; i ++ ) f[i] = f[i-1]+r-l+1;
    for(int i = 1; i <= n; i ++ ) {
        f2 t = ((f2)f[i-1]+f[n-i])/f[n];
        ans += 1-qp(t, m);
    }
    printf("%.3f\n", ans);
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<

发表评论

电子邮件地址不会被公开。 必填项已用*标注