|
||||||||||
生成树Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 1 Accepted Submission(s): 0 Problem Description 给出一张$n$个点$m$条边的无向图,第$i$条边连接$u,v$,在第$j$天出现的概率为$p_i+\frac{j}{k_i}$ 求这一张图从第一天到第$T$天每天期望生成树的个数的和,答案对$998244353$取模 注意图上可能会有重边出现,由于一些神奇的原因,若有重边出现两点之间有边的概率为所有重边概率相加的和 Input 第一行三个正整数 $n,m,T$ 接下来$m$行,每行$5$个整数$u_i,v_i,a_i,b_i,k_i$ 其中$p_i=\frac{a_i}{b_i}$,保证每个概率的实际值$\le 1$,给出的$a_i,b_i$仅代表模意义下 保证对于一条存在的边,其重边的$\sum \frac{1}{k_i} \neq 0$ $mod$ $998244353$ $2\leq n\leq 400,1\leq m \le 100000,1 \le u_i,v_i\le n,1\le a_i,b_i,k_i\le 10^8,1\le T \le 10^9$ Output 输出一个整数,表示要求的答案 Sample Input
Sample Output
Source | ||||||||||
|