BZOJ5091: [Lydsy1711月赛]摘苹果

### Description
小Q的工作是采摘花园里的苹果。在花园中有n棵苹果树以及m条双向道路，苹果树编号依次为1到n，每条道路的两
端连接着两棵不同的苹果树。假设第i棵苹果树连接着d_i条道路。小Q将会按照以下方式去采摘苹果：
1.小Q随机移动到一棵苹果树下，移动到第i棵苹果树下的概率为d_i/(2m)，但不在此采摘。
2.等概率随机选择一条与当前苹果树相连的一条道路，移动到另一棵苹果树下。
3.假设当前位于第i棵苹果树下，则他会采摘a_i个苹果，多次经过同一棵苹果树下会重复采摘。
4.重复第2和3步k次。
请写一个程序帮助计算小Q期望摘到多少苹果。
### Input
第一行包含三个正整数n,m,k(n,k<=100000,m<=200000)，分别表示苹果树和道路的数量以及重复步骤的次数。

第二行包含n个正整数，依次表示a_1,a_2,...,a_n(1<=a_i<=100)。
接下来m行，每行两个正整数u,v(1<=u,v<=n,u!=v)，表示第u和第v棵苹果树之间存在一条道路。
### Output
 若答案为P/Q，则输出一行一个整数，即P*Q^{-1} mod 1000000007(10^9+7)。

### Sample Input
3 4 2

2 3 4

1 2

2 3

3 1
## Sample Output
750000011

//期望为5.75=23/4=(23*250000002) mod 1000000007=750000011。

看到这么神奇的概率条件，可能是在凑什么东西？
我们先考虑一步，看看每一个点被走到的概率是什么。
列一下：
$$P(u)=\sum_{u\to v}\frac{d_v}{2m}\frac{1}{d_v}$$
$$P(u)=\sum_{u\to v}\frac{1}{2m}=\frac{d_u}{2m}$$
呃，好像就和开头的概率一毛一样？？？？
每个点每一步被走到的概率都一样，那期望就每一个算算期望加起来？？？
我交交试试……
A了……

```
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int n, m, k, u, v, ans, invm, d[maxn], w[maxn];
LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}
 
void Add(int & x, const int &b) {
    x += b; if(x >= mod) x -= mod;
}
 
int main() {
    scanf("%d%d%d", &n, &m, &k);
    invm = fpow(2 * m % mod, mod - 2);
    for(register int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
    for(register int i = 1; i <= m; ++i)
        scanf("%d%d", &u, &v), ++d[u], ++d[v];
    for(register int i = 1; i <= n; ++i)
        Add(ans, 1ll * d[i] * w[i] % mod);
    ans = 1ll * ans * invm % mod;
    ans = 1ll * ans * k % mod;
    printf("%d", ans);
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链