#include #include #include #include #include using namespace std; typedef long long LL; const int MAXN = 1e6 + 10; const int INF = 0x3f; int n, m; struct TA{ double a[MAXN]; double sum(int p){ double res = 0; for(;p;p-=(p&-p)){ res += a[p]; } return res; } void modify(int p,double val){ p++; for(;p<=n;p+=(p&-p)){ a[p] += val; } } }ta; struct Edge{ int u, v; double p; Edge(){} Edge(int u,int v,double p):u(u),v(v),p(p){} }e[MAXN]; bool cmp(Edge a,Edge b){ if(a.u != b.u)return a.u < b.u; return a.v < b.v; } double p; double powp[MAXN]; int deg[MAXN], cnt[MAXN]; int main() { cin >> n >> m >> p; for(int i = 0;i < m; i++){ int u, v; cin >> u >> v; u--; v--; deg[u]+=1; e[i] = Edge(u, v, 0); } sort(e,e + m, cmp); powp[0] = 1.0; for(int i = 0;i < n; i++){ powp[i + 1] = powp[i] * (1 - p); } memset(cnt, 0, sizeof(cnt)); for(int i = 0;i < m; i++){ int u = e[i].u; e[i].p = p * (powp[cnt[u]]) / (1 - powp[deg[u]]); cnt[u] += 1; } reverse(e, e + m); int pointer = 0; double res = 0.0; for(int i = n-1;i >= 0; i--){ for(int j = pointer;j < m && e[j].u == i; j++){ res += ta.sum(e[j].v) * e[j].p; } for(int j = pointer;j < m && e[j].u == i; j++){ ta.modify(e[j].v, e[j].p); pointer = j + 1; } } printf("%.2lf", res); return 0; }

首先，我们可以利用等比数列求和公式，因为 $0.4 \le p < 0.6$，删去分子上的 $A(q+1)$ 算出每对男女 $(i,j)$ 在一起的概率。询问时倒序插入并用树状数组维护。

比如对一个女生 $a$，有 $k$ 个候选男生编号为 $1$ 至 $k$。那么对于第 $m$ 个男生， $(a,m)$ 在一起的概率就是 $(1-p) ^ {m-1} \times p + (1-p)^k \times (1-p) ^ {m-1} \times p + (1-p)^{2k} \times (1-p) ^ {m-1} \times p + ...+(1-p)^{x-1}\times (1-p) ^ {m-1} \times p$

我们不妨先利用等比数列求和公式：

其中， $a_1 = (1-p)^{m-1} \times p,q = (1 - p)^k$。那么在 $n$ 很大时， $q^n$ 就非常接近 $0$。所以我们不妨将 $q^n$ 当作 $0$，呢么答案就是 $a_1 \div (1-q)$。

我们发现，这个思路只能拿到 60 分。我们可以倒叙枚举女生，使用树状数组维护后 $i$ 个女生和前 $j$ 个男生配对的概率和，这一题就做完了。

AC 代码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring> 
#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int INF = 0x3f;
int n, m;
struct TA{
	double a[MAXN];
	double sum(int p){
		double res = 0;
		for(;p;p-=(p&-p)){
			res += a[p];
		}
		return res;
	}
	void modify(int p,double val){
		p++;
		for(;p<=n;p+=(p&-p)){
			a[p] += val;
		}
	}
}ta;
struct Edge{
	int u, v;
	double p;
	Edge(){}
	Edge(int u,int v,double p):u(u),v(v),p(p){}
}e[MAXN];
bool cmp(Edge a,Edge b){
	if(a.u != b.u)return a.u < b.u;
	return a.v < b.v;
} 
double p;
double powp[MAXN];
int deg[MAXN], cnt[MAXN];
int main()
{
	cin >> n >> m >> p;
	for(int i = 0;i < m; i++){
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		deg[u]+=1;
		e[i] = Edge(u, v, 0);
	}
	sort(e,e + m, cmp);
	powp[0] = 1.0;
	for(int i = 0;i < n; i++){
		powp[i + 1] = powp[i] * (1 - p);
	}
	memset(cnt, 0, sizeof(cnt));
	for(int i = 0;i < m; i++){
		int u = e[i].u;
		e[i].p = p * (powp[cnt[u]]) / (1 - powp[deg[u]]);
		cnt[u] += 1;
	}
	reverse(e, e + m);
	int pointer = 0;
	double res = 0.0;
	for(int i = n-1;i >= 0; i--){
		for(int j = pointer;j < m && e[j].u == i; j++){
			res += ta.sum(e[j].v) * e[j].p;
		}
		for(int j = pointer;j < m && e[j].u == i; j++){
			ta.modify(e[j].v, e[j].p);
			pointer = j + 1;
		}
	}
	printf("%.2lf", res);
    return 0;
}

我的博客中观看：https://caijacky-note.blog.luogu.org/solution-p6089