BZOJ 5091: [Lydsy1711月赛]摘苹果 概率

推一推式子后发现每个点不论走几步被访问到的概率都是 $frac{d_{i}}{2m}$  

code:

#include <cstdio>  
#include <string>   
#include <algorithm>  

#define N 100070 
#define ll long long 
#define mod 1000000007 
using namespace std; 
int a[N],d[N];  
namespace IO { 
    void setIO(string s) 
    {
        string in=s+".in"; 
        string out=s+".out"; 
        freopen(in.c_str(),"r",stdin); 
    }
}; 
ll qpow(ll x,ll y) 
{
    ll ans=1; 
    while(y) 
    {
        if(y&1) ans=ans*x%mod;  
        x=x*x%mod,y>>=1;  
    } 
    return ans; 
}
int main() 
{ 
    // IO::setIO("input");  
    int n,m,k,i,x,y;  
    ll ans=0; 
    scanf("%d%d%d",&n,&m,&k);   
    for(i=1;i<=n;++i) scanf("%d",&a[i]); 
    for(i=1;i<=m;++i) scanf("%d%d",&x,&y),++d[x],++d[y];   
    for(i=1;i<=n;++i) ans+=a[i]*d[i];   
    printf("%lld
",ans*k%mod*qpow(2*m,mod-2)%mod);   
    return 0; 
}