該題很容易想到求概率的轉移方程：用d[i][j]表示第i步，走到j點的概率。 但是該題的k高達1e9，所以按照套路，要用矩陣相乘來優化。 第一次寫矩陣相乘， 大概的意思就是利用矩陣實現遞推， 并且因為每次遞推的過程一樣， 所以就相當于右乘這個矩陣的k次方。 用矩陣快速冪即可。 矩陣相乘這個問題， 大概可以看成， 矩陣中的每個元素表示到該點的概率， 那么另一個矩陣就是DP矩陣， 表示當前一步到各點的概率， 矩陣相乘就等于下一步到各點的概率（矩陣乘法的意義）。 另外， 要對答案進行1e9+5次方再取模， 如果最后取模， 那么將對分母Y進行取模后再次方再取模， 這是和原問題不等價的， 所以解決方法是按照乘法取模公式， 先對矩陣元素提前處理該操作。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int mod = 1000000000 + 7; const int maxn = 1000 + 10; ll T,n,q,u,k,m,x,y,cnt[maxn]; vector<ll> g[maxn]; typedef vector<ll> vec; typedef vector<vec> mat; mat mul(mat &a, mat &b) { mat c(a.size(), vec(a.size())); for(int i=1;i<=n;i++) { for(int k=1;k<=n;k++) { for(int j=1;j<=n;j++) { c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod; } } } return c; } mat pow(mat a, ll k) { mat b(a.size(), vec(a.size())); for(int i=1;i<=n;i++) { b[i][i] = 1; } while(k > 0) { if(k & 1) b = mul(b, a); a = mul(a, a); k >>= 1; } return b; } ll mod_pow(ll x, ll n, ll mod) { ll res = 1; while(n > 0) { if(n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main() { while(~scanf("%I64d%I64d",&n,&m)) { for(int i=1;i<=n;i++) g[i].clear(); memset(cnt, 0, sizeof(cnt)); mat a(n+3, vec(n+3)); for(int i=0;i<m;i++) { scanf("%I64d%I64d",&x,&y); g[y].push_back(x); a[y][x] = 1; cnt[x]++; } for(int i=1;i<=n;i++) { cnt[i] = mod_pow(cnt[i], 1000000005, mod); } for(int i=1;i<=n;i++) { int len = g[i].size(); for(int k=0;k<len;k++) { a[i][g[i][k]] = (a[i][g[i][k]] * cnt[g[i][k]]) % mod; } } scanf("%I64d",&q); while(q--) { scanf("%I64d%I64d",&u,&k); mat hehe = pow(a, k); for(int i=1;i<=n;i++) { printf("%I64d ", hehe[i][u]); } printf("\n"); } } return 0; } ~~~