题意
一共有\(N\)位客人和\(M\)本书，他们都希望能够找到一本适合自己的书。
\(1\sim N\)的书都被编上了一个号码，并且每本书的编号不一样。
每个客人都有一个选书列表，对于每一本书，他有\(p\)的概率选择这本书（换言之，会以\(1-p\)的概率拒绝这本书）。
如果他拒绝这本书，他就会去看下一本书，如果他不选最后一本书，则他又会从第一本书开始选书，直到他找到一本适合自己的书。
当然，两个客人可能选到同一本书。
在考虑任意两个不同的客人\(a\)和\(b\)，如果\(a\)的编号比\(b\)的编号小，而\(a\)选择的书的编号比\(b\)选择的编号大，那么\(a\)和\(b\)就叫做一对不稳定因素。
店主希望求出不稳定因素的期望数目。
思路
考虑一个人在它的列表中选第\(1\)本书的概率。假设他的列表长度为\(k\)
\(g(1)=P+(1?P)^kP+(1?P)^{2k}P+...\)
即\(g(1)=P\frac{1-(1-P)^\infty}{1-(1-P)^k}=\frac{P}{1-(1-P)^k}\)，接下来可以推出\(g(i)=g(i-1)*(1-p)\)。
然后从小到大考虑每个客人，用树状数组维护答案即可。
代码
#include <vector>
#include <cstdio>
#include <algorithm>
#define double long double
int n, m;
double p;
double t[500001];
std::vector<int> a[500001];
double ans;
double power(double a, int b) {
double res = 1;
for (; b; b >>= 1) {
if (b & 1)
res *= a;
a *= a;
}
return res;
}
void add(int x, double val) {
for (; x <= n; x += x & -x)
t[x] += val;
}
double query(int x) {
double res = 0;
for (; x; x -= x & -x)
res += t[x];
return res;
}
int main() {
scanf("%d %d", &n, &m);
scanf("%Lf", &p);
for (int i = 1, x, y; i <= m; i++) {
scanf("%d %d", &x, &y);
a[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
if (a[i].empty())
continue;
std::sort(a[i].begin(), a[i].end());
double now = p / (1 - power(1 - p, a[i].size()));
for (int j = 0; j != a[i].size(); j++) {
ans += (query(n) - query(a[i][j])) * now;
now *= 1 - p;
}
now = p / (1 - power(1 - p, a[i].size()));
for (int j = 0; j != a[i].size(); j++) {
add(a[i][j], now);
now *= 1 - p;
}
}
printf("%.2Lf", ans);
}