graph
Accepts: 9
Submissions: 61
Time Limit: 8000/4000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
在一个NN个点(标号11~nn),MM条边的有向图上,一开始我在点uu,每一步我会在当前点的出边中等概率的选一条走过去,求走了恰好KK步后走到每个点的概率.
输入描述
第一行两个正整数N,MN,M,表示点数和边数.接下来MM行,每行两个正整数X,YX,Y.表示一条XX向YY的一条有向边(保证没有重边和自环).接下来一个正整数QQ,表示询问个数.接下来QQ行,每行两个正整数u,Ku,K,表示开始的点和步数.N \leq 50, M \leq 1000, Q \leq 20, u \leq n, K \leq 10^{9}N≤50,M≤1000,Q≤20,u≤n,K≤109.每个点保证至少有一个出边. 输出描述
QQ行,每行NN个数字,用空格隔开,第ii个数字表示从uu开始走KK步到ii的概率.考虑到输出的答案可能会有精度问题,经过一定的分析后可以发现答案一定可以被表示成\frac{X}{Y}YX的形式,你只需输出X \times Y^{10^9+5} \ mod \ (10^9+7)X×Y109+5 mod (109+7)的值即可.在每行后面多输出一个空格,否则可能会使你PE. 输入样例
3 21 21 311 1
输出样例
0 500000004 500000004
Hint
这是一个三个点,两条边的有向图,它们分别是(1->2,1->3)(1−>2,1−>3).现在在1号点,走了一步后,有1/2的概率走到了2,有1/2的概率走到了3,本来应该输出 0 0.5 0.5而根据上面所说的,应输出1*2^{10^9+5} \ mod \ (10^9+7)=5000000041∗2109+5 mod (109+7)=500000004.
思路：
矩阵经典问题：求从i点走k步后到达j点的方案数(mod p)。
本题输出X/Y,可以看成X是u走k步到j的方案数,Y是从u走k步的所有方案数
于是对矩阵先进行处理,即给m[i][j]乘上节点i的出度的1e9+5次方。
(ma.m[i][j]*(ll)pow_mod(g[i],1e9+5,MOD))%MOD;
再用矩阵快速幂即可
#include#include #include #include #include #include using namespace std;typedef long long ll;typedef long double ld;const ld eps=1e-10;const int inf = 0x3f3f3f;const int maxn = 55;const int MOD = 1e9+7;ll n;int g[55];struct Matrix{ ll m[maxn][maxn]; Matrix() { memset(m,0,sizeof(m)); }};Matrix multi(Matrix a,Matrix b,ll mod){ Matrix tmp; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { for(int k = 1; k <= n; k++) { tmp.m[i][j] = (tmp.m[i][j]+(a.m[i][k] * b.m[k][j])%mod)%mod; } } } return tmp;}Matrix Pow(Matrix a,int m,int p){ Matrix t; for(int i = 1; i <= n; i++) t.m[i][i] = 1; while(m) { if(m & 1) { t = multi(t,a,p); m-=1; } a = multi(a,a,p); m >>= 1; } return t;}ll pow_mod(ll a,ll m,ll p){ a %= p; ll t = 1; while(m) { if(m & 1) { t = t * a%p; m-=1; } a = a*a%p; m >>= 1; } return t%p;}int main(){ ll m; int a,b; int q,k,u; while(scanf("%I64d%I64d",&n,&m) != EOF) { Matrix ma; memset(g,0,sizeof(g)); for(int i = 0; i < m; i++) { scanf("%d%d",&a,&b); ma.m[a][b] ++; g[a] ++; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { ma.m[i][j] = (ma.m[i][j]*(ll)pow_mod(g[i],1e9+5,MOD))%MOD; } } scanf("%d",&q); while(q--) { scanf("%d%d",&u,&k); Matrix tans =Pow(ma,k,MOD); for(int j = 1; j <= n; j++) { printf("%I64d ",tans.m[u][j]%MOD); } printf("\n"); } } return 0;}