JSOI2015 非诚勿扰

参考了 万弘 神仙的题解

假设一个女性中意(k)个男性

第一个男性被选中的概率为(g(1)=P+(1-P)^kP+(1-P)^{2k}P+...)

根据等比数列求和，(large g(1)=Pfrac{1-(1-P)^{infty}}{1-(1-P)^k})，无穷次方视为(0)，(large g(1)=Pfrac1{1-(1-P)^k})

(large g(i)=g(i-1) imes(1-P))，可以求出(g(i))

从小到大考虑每个女性(i)，若选择第(j)个中意的男性，记为((a_{i,j}))，贡献为

[largesum_{a<i}sum_{b>a_{i,j}}P(a选b) imes g(j) ]

单点加，询问后缀和，树状数组维护 (O(mlog n))

ld tre[N]; int n;
void add(int x,ld a){
	for(;x <= n;x += x &-x) tre[x] += a;
}
ld query(int x){
	ld res = 0;
	for(;x;x -= x&-x) res += tre[x];
	return res;
}
vector<int>a[N];
ld Qpow(ld x,int b){
	ld res = 1;
	for(;b;b >>= 1){
		if(b & 1) res *= x;
		x *= x;
	} return res;
}
int main(){
	n = read();
    int m = read(); double tmp;
    scanf("%lf",&tmp);
    long double p=tmp,ans=0;
    for(int i = 1;i <= m;++i){
        int u = read(),v = read();
        a[u].push_back(v);
    }
    for(int u = 1;u <= n;++u){
        if(a[u].empty())continue;
        sort(a[u].begin(),a[u].end());
        long double now = p/(1-Qpow(1-p,a[u].size()));
        for(int v:a[u]){
            ans += query(n-v)*now;
            now *= (1-p);
        }
        now = p/(1-Qpow(1-p,a[u].size()));
        for(int v:a[u]){
            add(n-v+1,now);
            now *= (1-p);
        }
    }
    printf("%.2Lf",ans);
}