BZOJ2698:染色 期望

思路:

考虑到每个格子的贡献是独立的,我们分别考虑每个格子.

那么这个格子最终产生贡献的概率如何求呢?显然其等于\(1\)减去这个格子在\(m\)次染色后还没有被染色的概率.

这个格子一次染色没有被染色的概率为\(p\)的话,这个格子的贡献就为\(1*(1-p^m)\).

这样就可在\(O(n)\)内出解了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
f2 ksm(f2 x,int y){
    f2 r=1,t=x;for(;y;y>>=1,t*=t)if(y&1)r*=t;return r;
}
long long calc(int len,int l,int r){
    if(l>len)return 0;
    r=min(r,len);
    return (long long)(r-l+1)*(len+1)-(long long)(l+r)*(r-l+1)/2;
}
 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    int n,m,l,r;cin>>n>>m>>l>>r;
    long long total=0,resl,resr;f2 p,ans=0;
    for(int i=l;i<=r;++i)total+=n-i+1;
    for(int i=1;i<=n;++i){
        resl=calc(i-1,l,r),resr=calc(n-i,l,r);
        p=(resl+resr)/(double)total;
        ans+=1-ksm(p,m);
    }
    printf("%.3lf",ans);
    return 0;
}