【BZOJ5091】摘苹果
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
2 3 4
1 2
1 2
2 3
3 1
Sample Output
750000011
//期望为5.75=23/4=(23*250000002) mod 1000000007=750000011。
//期望为5.75=23/4=(23*250000002) mod 1000000007=750000011。
题解：一开始停留在每个点的概率是$frac {d_i} {2m}$。来，我们算一下第一次操作后停留在每个点的概率：$p_i=sumlimits_{<i,j>}{{d_jover 2m}over d_j}={d_iover 2m}$。好像。。。不变？这不就做完了嘛！
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll P=1000000007;
const int maxn=100010;
int n,m;
ll k,ans;
int d[maxn];
ll v[maxn];
inline ll pm(ll x,ll y)
{
ll z=1;
while(y)
{
if(y&1) z=z*x%P;
x=x*x%P,y>>=1;
}
return z;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd(),k=rd();
int i,a,b;
for(i=1;i<=n;i++) v[i]=rd();
for(i=1;i<=m;i++) a=rd(),b=rd(),d[a]++,d[b]++;
for(i=1;i<=n;i++) ans=(ans+1ll*d[i]*v[i]%P*k)%P;
ans=ans*pm(m<<1,P-2)%P;
printf("%lld",ans);
return 0;
}