牛客练习赛74 CCA的期望(累加期望和)

传送门

求期望的套路题

转化为每个点染成黑色期望的累加和

那么如果本来就是黑色,期望直接加上 $1$

如果是白色,概率是多少呢??实际上可以考虑这个点在多少的最短路径上

选点有 $x=\frac{n*(n-1)}{2}$ 种方式

再计算有 $y$ 条最短路径经过这个点,那么一次操作覆盖这个点概率为 $\frac{y}{x}$

那么至少覆盖一次期望就是 $1-(\frac{y}{x})^k$

累加即可

至于一个点在多少最短路径上,弗洛伊德即可

然后这样判断 $dis[i][j]==dis[i][k]+dis[k][j]$

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dis[509][509],n,m,k,color[509],vis[509];
const int mod = 1023694381;
int quick(int x,int n)
{
    int ans = 1;
    for( ; n ; n>>=1,x=x*x%mod )
        if( n&1 )    ans = ans*x%mod;
    return ans;
}
signed main()
{
    cin >> n >> m >> k;
    if( n>500 )
    {
        while(1  )    int s;
    }
    for(int i=1;i<=n;i++)    cin >> color[i];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if( i!=j )    dis[i][j] = 1e16;
    for(int i=1;i<=m;i++)
    {
        int l,r,w; cin >> l >> r >> w;
        dis[l][r] = dis[r][l] = min( dis[l][r],w );
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        dis[i][j] = min( dis[i][j],dis[i][k]+dis[k][j] );
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        for(int k=1;k<=n;k++)
            if( dis[i][j]==dis[i][k]+dis[k][j] ) vis[k]++;
    }
    int ans = 0, inv = quick(n*(n-1)/2,mod-2);
    for(int i=1;i<=n;i++)
    {
        if( color[i]==1 )    ans = ( ans+1 )%mod;
        else
        {
            int p = 1-quick(n*(n-1)/2-vis[i],k)*quick(inv,k)%mod;
            ans = ( ans+p )%mod;
        }
    }
    cout << (ans%mod+mod)%mod;
}