【BZOJ5091】摘苹果

题目：

这题一拿上来，估计大家都能想到的是概率期望题目中有

那么接下来就是一顿推柿子……

设在每个点停留的概率为 \(P(i)\)

则 \(P(i)=\sum_{<i,j>}\frac{\frac{d_j}{2m}}{d_j}=\sum_{<i,j>}\frac{1}{2m}=\frac{d_i}{2m}\)，其中\(<i,j>\)表示一条边的两个顶点

其中第一个等号右侧为从其他点转移到这个点的概率，最后一次变换利用定义，可以发现最后只剩下\(\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
*/

完美撒花~

【BZOJ5091】摘苹果

原文：https://www.cnblogs.com/Sam2007/p/12426529.html