HDU 5607 graph（DP+矩阵乘法）

【题目链接】

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=663&pid=1002

【题意】

给定一个有向图，若干个询问，问从u走k步到达各个顶点的概率。

其中除法化为乘逆元。

【思路】

设f[i][j]表示到达i点走了j步的概率，则有转移式：

f[i][j]=sigma{ f[pre(i)][j-1]/out[pre(i)] }

其中pre为有向图上的前一个节点，out[u]为u的出度大小。

构造矩阵后使用矩阵乘法加速状态转移。

设e为转移矩阵，若ij相连则e[i][j]<-out[i]^-1，否则为0。

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 const int maxn = 55;
 9 const int MOD = 1e9+7;
10 
11 struct Matrix {
12     int r,c; ll N[maxn][maxn];
13     void init(int r,int c) {
14         this->r=r,this->c=c;
15         memset(N,0,sizeof(N));
16     }
17     Matrix operator * (const Matrix& B) const{
18         Matrix C;
19         C.init(r,B.c);
20         FOR(i,1,r) FOR(j,1,c) FOR(k,1,C.c)
21             C.N[i][j]=(C.N[i][j]+(ll)N[i][k]*B.N[k][j])%MOD;
22         return C;
23     }
24     Matrix pow(int p) {
25         Matrix tmp=*this,ans;
26         ans.init(r,r);
27         FOR(i,1,r) ans.N[i][i]=1;
28         while(p) {
29             if(p&1) ans=ans*tmp;
30             tmp=tmp*tmp;
31             p>>=1;
32         }
33         return ans;
34     }
35 }f,e,t;
36 ll pow(ll x,ll p) {
37     ll tmp=x,ans=1;
38     while(p) {
39         if(p&1) ans=(ans*tmp)%MOD;
40         tmp=(tmp*tmp)%MOD; p>>=1;
41     }
42     return ans;
43 }
44 
45 int n,m,q;
46 int a[maxn][maxn],out[maxn];
47 
48 int main()
49 {
50     scanf("%d%d",&n,&m);
51     int u,v,k;
52     FOR(i,1,m) {
53         scanf("%d%d",&u,&v);
54         a[u][v]=1; out[u]++;
55     }
56     e.init(n,n);
57     FOR(i,1,n) {
58         out[i]=pow(out[i],MOD-2);
59         FOR(j,1,n) if(a[i][j]) {
60             e.N[i][j]=out[i];
61         }
62     }
63     scanf("%d",&q);
64     while(q--) {
65         scanf("%d%d",&u,&k);
66         f.init(1,n); f.N[1][u]=1;
67         t=e.pow(k);
68         f=f*t;
69         FOR(i,1,n) printf("%I64d ",f.N[1][i]);
70         puts("");
71     }
72     return 0;
73 }