题目
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。
题解
感觉思路很神仙啊orz
设$f_{i,j}$表示第$i$棵树，移动了$j$次摘到苹果的期望值，则有： $f_{i,j}=\sum_{(v,j)\in e}\frac{f_{i-1,v}}{d_v},ans=\sum_{i=1}^{n}\sum_{j=1}^{k}f_{j,i}\times a_i$，但是$n,m$非常大，显然不是这么做
有什么优化方法吗？
初始一次没走的时候，即$f_{0,j}=\frac{d_j}{2m}$，第一步走每条边的概率是相等的，即$\frac{d_j}{2m}\times \frac{1}{d_j}=\frac{1}{2m}$
那么走第一步的时候期望为$f_{1,j}=\sum_{(v,j)\in e}\frac{1}{2m}=\frac{d_j}{2m}$
诶怎么$f_{1,j}=f_{0,j}$？
所以$f_{i,j}=f_{i-1,j}=\frac{d_j}{2m}$，则有$ans=\sum_{i=1}^{n}\sum_{j=1}^{k}f_{j,i}\times a_i=k\times \sum_{i=1}^{n}\frac{d_ia_i}{2m}$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e5+5,mod=1e9+7;
int n,m,k;
int a[MAX],du[MAX];
int Pow(int x)
{
int b=mod-2,ans=1;
for(;b;b>>=1,x=1ll*x*x%mod)
if(b&1) ans=1ll*ans*x%mod;
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1,x,y;i<=m;++i)
scanf("%d%d",&x,&y),++du[x],++du[y];
int qwq=Pow(2*m),ans=0;
for(int i=1;i<=n;++i)
{
ans+=1ll*du[i]*a[i]%mod*qwq%mod;
if(ans>=mod) ans-=mod;
}
return printf("%lld",1ll*k*ans%mod),0;
}
