当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5607:graph

题目描述
In a directed graph which has $N$ points and $M$ edges,points are labled from 1 to n.At first I am at point $u$,at each step I will choose an output edge of the current point at uniform random,for every point $Z$,please output the possibility of reaching the point $Z$,moving exactly $K$ steps.
输入解释
the first line contains two positive interges$N,M$,means the number of points and edges.

next $M$ lines,contains two positive intergers$X,Y$,means an directed edge from X to Y.

next line there is an integer $Q$,means the number of queries.

next $Q$ lines,each line contains two integers $u,K$,means the first point and number of the steps.

$N\le 50,M\le 1000,Q\le 20,u\le N,K\le 10^9$.

Every point have at least one output edge.
输出解释
$Q$ lines,each line contains $N$ numbers,the $i$-th number means the possibility of reaching point $i$ from $u$,moving exactly $K$ steps.

In consideration of the precision error,we make some analyses,finding the answer can be represented as the form like $\frac{X}{Y}$,you only need to output $X\times Y^{10^9+5}~mod~(10^9+7)$.

You need to output an extra space at the end of the line,or you will get PE.
输入样例
3 2
1 2
1 3
1
1 1
输出样例
0 500000004 500000004 

I am now at point $1$,by one move,with a possibity of $\frac{1}{2}$ of reaching point 2,with a possibity of $\frac{1}{2}$ of reaching point 3,so we need to output 0 0.5 0.5,but as what is said above,we need to output$1*2^{10^9+5}~mod~{10^9+7}=500000004$.
来自杭电HDUOJ的附加信息
Recommend hujie

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-5607

最后修改于 2020-10-25T23:24:09+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
8000/4000MS(Java/Others) 65536/65536K(Java/Others)