乐清站在那儿,国际网站怎么开通,wordpress注册登录修改,优化大师如何删掉多余的学生牛客地址 题目描述 是否经常有艺术创作的冲动#xff0c;但却限于水平无法描绘#xff1f;那就交给随机吧#xff01; 给定一张 n 个点 m 条边的无向带边权连通图#xff0c;点有颜色#xff0c;为黑或白#xff0c;保证无自环和重边。 定义一次操作为#xff1a;随机选…牛客地址 题目描述 是否经常有艺术创作的冲动但却限于水平无法描绘那就交给随机吧 给定一张 n 个点 m 条边的无向带边权连通图点有颜色为黑或白保证无自环和重边。 定义一次操作为随机选择两个不同的点将它们之间的最短路上的点全部染黑若有多条最短路就都染黑。 现在你想知道经过 k 次操作后黑色点的期望个数是多少 。
思路算这个的期望我们可以转化为每个点对期望的贡献既算出每个点变成黑色的概率。 任意选择两个不同的点那么就有总数 cntn*n-1/2 假设经过i点的最短数次数为y这个可以由floyd算法算出 如果该点的颜色本来就为黑色那么期望贡献为1 否则选择k次至少一次选择的路径含有该点的期望就为1-1-y/cnt^k(连续k次都没有选择到 反向思考) 取模除法要使用逆元 细节看代码
#include cstdio
#include cstring
#include string
#include cmath
#include iostream
#include algorithm
#include queue
#include cstdlib
#include stack
#include vector
#include set
#include map
#include bitset
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
const ll mod1023694381;
const ll N 3e610;
const double eps 1e-6;
const double piacos(-1);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
int dx[8] {1,0,-1,0,1,1,-1,-1}, dy[8] {0,1,0,-1,1,-1,1,-1};
int n,m,k;
ll dis[1000][1000];
int c[1000];
int sum[1000];
ll pow1(ll a,ll b){ll ans1;while(b){if(b1) ans(ans*a)%mod;a(a*a)%mod;b/2;}return ans;
}
void floyd()
{for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){dis[i][j]min(dis[i][k]dis[k][j],dis[i][j]);}}}
}
void solve()
{cinnmk;for(int i1;in;i){for(int j1;jn;j){if(ij) dis[i][j]0;else dis[i][j](ll)1e15;}}for(int i1;in;i) cinc[i];for(int i1;im;i){ll u,v,w;cinuvw;dis[u][v]w;dis[v][u]w;}floyd();for(int i1;in;i){for(int ji1;jn;j){for(int k1;kn;k){if(dis[i][j]dis[i][k]dis[k][j]) sum[k];}}}ll cnt((n-1)*n)/2;ll invpow1(pow1(cnt,k),mod-2)%mod;ll ans0;for(int i1;in;i){if(c[i]1) ans(ans1)%mod;else{ans(ans((1-(pow1(cnt-sum[i],k)*inv)%modmod)%mod))%mod;}}coutansendl;
}
int main()
{iosint T;//cinT;T1;while(T--){solve();}return 0;
}
