给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值 把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。
此题就是此类经典矩阵快速幂题
code:
#include<stdio.h> #include<string.h> const int N=25; #define mod 1000 int n,m; struct Matrix { int mat[N][N]; Matrix() { memset(mat,0,sizeof(mat)); } }; Matrix mul(Matrix a,Matrix b) { Matrix res; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int k=0;k<n;k++) { res.mat[i][j]+=(a.mat[i][k]*b.mat[k][j])%mod; res.mat[i][j]%=mod; } } } return res; } Matrix pow(Matrix a,int k) { Matrix res; for(int i=0;i<n;i++) { res.mat[i][i]=1; } while(k) { if(k&1) res=mul(res,a); a=mul(a,a); k>>=1; } return res; } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) { break; } Matrix A,B; int x,y; while(m--) { scanf("%d%d",&x,&y); A.mat[x][y]=1; } int T,k; scanf("%d",&T); while(T--) { scanf("%d%d%d",&x,&y,&k); B=pow(A,k); printf("%d\n",B.mat[x][y]%mod); } } }