题目传送门(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 longinline 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原创, 转载必须以链接形式注明>原文链接<