2019-05-01 00:11 阅读 127


Problem Description
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 intergesN,M,means the number of points and edges.

next M lines,contains two positive intergersX,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.


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 XY,you only need to output X×Y109+5 mod (109+7).

You need to output an extra space at the end of the line,or you will get PE.

Sample Input
3 2
1 2
1 3
1 1

Sample Output
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$.

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享