BZOJ5091: [Lydsy1711月赛]摘苹果【期望DP】

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

1 2

2 3

3 1

Sample Output

750000011

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

思路

拆开看每个节点的贡献

设\(f_{i,j}\)表示在第j步走到i点的概率

\(f_{i,0}=\frac{d_i}{2m}\)

那么\(f_{i,1}=\sum_{i,j\in E}\frac{f_{j,0}}{d_j}=\frac{d_i}{2m}\)

所以得到\(f_{i,j\in[0,k]}=\frac{d_i}{2m}\)

然后又因为每个树的贡献是\(a_i*\sum_{i=1}^kf_{i,k}=\frac{a_i*d_i*k}{2m}\)

然后就直接算就行了

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

const int Mod = 1e9 + 7;

int add(int a, int b) {

  return (a += b) >= Mod ? a - Mod : a;

}

int mul(int a, int b) {

  return 1ll * a * b % Mod;

}

int fast_pow(int a, int b) {

  int res = 1;

  while (b) {

    if (b & 1) res = mul(res, a);

    b >>= 1;

    a = mul(a, a);

  }

  return res;

}

int n, m, k, d[N], a[N];

int main() {

  scanf("%d %d %d", &n, &m, &k);

  for (int i = 1; i <= n; i++) {

    scanf("%d", &a[i]);

  }

  for (int i = 1; i <= m; i++) {

    int u, v; scanf("%d %d", &u, &v);

    d[u]++;

    d[v]++;

  }

  int cur = 0;

  for (int i = 1; i <= n; i++) {

    cur = add(cur, mul(a[i], d[i]));

  }

  printf("%d", mul(cur, mul(k, fast_pow(m * 2, Mod - 2))));

  return 0;

}

巴特西