BZOJ5091摘苹果（概率、期望）

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=5091

题目告诉我们，初始选每一个点的概率为d_i/2m，那么走一次到达某个点u的概率为

这不是和初始选点的概率一样了么。。。。结束。。。。

代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 using namespace std;
  5 
  6 typedef long long LL;
  7 const LL p = (LL)1e9 + 7;
  8 LL n, m, k, E;
  9 LL arr[100005], degree[100005];
 10 
 11 void exGCD(LL a, LL b, LL &d, LL &x, LL &y)
 12 {
 13 	if(!b) d = a, x = 1, y = 0;
 14 	else
 15 	{
 16 		exGCD(b, a % b, d, y, x);
 17 		y -= a / b * x;
 18 	}
 19 }
 20 LL Inverse(LL _x)
 21 {
 22 	LL d, x, y;
 23 	exGCD(_x, p, d, x, y);
 24 	if(x < 0) x += p;
 25 	return x;
 26 }
 27 int main()
 28 {
 29 	scanf("%lld%lld%lld", &n, &m, &k);
 30 	for(LL i = 1; i <= n; i++)
 31 		scanf("%lld", arr + i);
 32 	for(LL i = 0; i < m; i++)
 33 	{
 34 		LL x, y;
 35 		scanf("%lld%lld", &x, &y);
 36 		degree[x]++, degree[y]++;
 37 	}
 38 	for(LL i = 1; i <= n; i++)
 39 		E = (E + degree[i] * arr[i]) % p;
 40 	printf("%lld
", E * k % p * Inverse(m * 2) % p);
 41 
 42 	return 0;
 43 }//Rhein_E

View Code