本文共 2334 字，大约阅读时间需要 7 分钟。

选书问题 / 非诚勿扰

题目链接： /

题目大意

就是有两种点，第一种的点会与一些第二种点连接，然后对于每一个连着的第二种点，这个第一种的点会有 p 的概率选择这个点，否则就跳到下一个和它连着的点。然后如果一直到最后一个都不选，就跳到第一个继续。

思路

我们看第一种点连着 $k$ 个第二种点。

然后我们来看选中第 $i$ 个第二种点的概率。

它第一轮被选中的概率是 $p$，第二轮是 $(1-p{)}^{k}p$，第三轮是 $(1-p{)}^{2k}p$，以此类推。

那我们根据和等于 $\frac{a_1(1-q^n)}{1-q}$，可以把式子变成这个：

因为 $1-p$ 是一个大于零小于一的数，所以它的无限次方就无限趋近与零，那一减它就是无限趋近于一咯。

那我们就得出了第一个点被选中的概率，那怎么求第二个、第三个这些点的概率呢？

第 $i$ 个被选到的概率就是 $\frac{p\times (1-p{)}^{i-1}}{1-(1-p{)}^k}$。

求次方很明显用快速幂，那我们就可以求出概率了。

接下来，我们来看期望怎么求。

看到题目要求逆序对，我们会很自然地想到求逆序对的树状数组。

然后有一点要注意的就是题目会卡精度，用 long double 来解决。

代码

#include
   
    #include
    
     #include
     
      using namespace std;int n, m, x, y, size;vector 
      
        a[500001];long double p, re, ans, tree[500001], thi;void build(int x, long double y) {   //树状数组	for (int now = x; now <= 500000; now += now & (-now))		tree[now] += y; }long double ask(int x) {   	re = 0;	for (int now = x; now; now -= now & (-now))		re = re + tree[now];	return re;}long double ksm(long double x, int y) {   //快速幂	re = 1.0;	while (y) {   		if (y & 1) re = re * x;		x = x * x;		y >>= 1;	}	return re;}int main() {   	scanf("%d %d", &n, &m);	scanf("%Lf", &p);		for (int i = 1; i <= m; i++) {   		scanf("%d %d", &x, &y);		a[x].push_back(y);	}		for (int i = 1; i <= n; i++)		sort(a[i].begin(), a[i].end());		ans = 0.0;	for (int i = 1; i <= n; i++) {   		size = a[i].size();		for (int j = 0; j < size; j++) {   			thi = p * ksm(1.0 - p, j) / (1.0 - ksm(1.0 - p, size));//算出来的概率			ans += (ask(m) - ask(a[i][j])) * thi;			build(a[i][j], thi);		}	}		printf("%.2Lf", ans);		return 0;}