题目:
这题一拿上来,估计大家都能想到的是概率期望题目中有
那么接下来就是一顿推柿子……
设在每个点停留的概率为 \(P(i)\)
则 \(P(i)=\sum_{<i,j>}\frac{\frac{d_j}{2m}}{d_j}=\sum_{<i,j>}\frac{1}{2m}=\frac{d_i}{2m}\)
其中第一个等号右侧为从其他点转移到这个点的概率,最后一次变换利用定义,可以发现最后只剩下\(\frac{d_i}{2m}\),跟其他点毫无关系
本题可以先求分子,再求分母的数论倒数,相乘即可
Warning:形如\(a^{-1}\)的且有模数的可能是数论倒数!!!,害得我一下子没看懂样例!!!
上代码我就知道你们只看这个
#include<bits/stdc++.h>
namespace kwx {
using namespace std;
#define LL long long
inline LL read() {
char c=getchar();
LL sum=0;
while(c<'0'||c>'9') {
c=getchar();
}
while(c>='0'&&c<='9') {
sum=(sum<<3)+(sum<<1)+c-'0',c=getchar();
}
return sum;
}
inline void write(LL x) {
if(x>9) {
write(x/10);
}
putchar(x%10+'0');
}
}
using namespace kwx;
const int N=1e5+5,mod=1e9+7;
LL a[N],d[N];
inline LL qpow(LL x,LL y) {
LL ans=1;
while(y) {
if(y&1) {
ans=x*ans%mod;
}
x=x*x%mod,y>>=1;
}
return ans;
}
int main() {
LL n=read(),m=read(),k=read();
// LL n,m,k;
// scanf("%lld %lld %lld",&n,&m,&k);
for(int i=1; i<=n; i++) {
a[i]=read();
// scanf("%lld",a+i);
}
for(int i=1,x,y; i<=m; i++) {
x=read(),y=read(),d[x]++,d[y]++;
}
LL ans=0;
for(int i=1; i<=n; i++) {
ans=(ans+d[i]*k%mod*a[i]%mod)%mod;
}
ans=ans*qpow(m<<1,mod-2)%mod;
write(ans);
return 0;
}
/*
3 4 2
2 3 4
1 2
1 2
2 3
3 1
*/
完美撒花~