题目：

　　

题意：

　　找过k条边的路径个数。

分析：

　　首先注意一下题意，同一个点过两次算两次，做过类似的，过k条边的最短路，只要搞一个矩阵，然后快速幂就好了，这个也一样，维护信息变一下，然后就好了。

　　如果k很大：

　　　　并不影响此种做法。

　　如果n很大：

　　　　改成dp。dp[x][k]表示过k个边到点x的路径数，然后就可以了。

代码：

#include
#include
#include
using namespace std;
const int maxn=+;
const int maxm=+;
int ed[maxm][maxm];
int n;
struct JZ{
int a[maxm][maxm];
JZ(){
memset(a,,sizeof(a));
}
JZ(int s){
for(int i=;i<=n;i++) for(int j=;j<=n;j++) a[i][j]=ed[i][j]; } JZ(int s,int k){ memset(a,,sizeof(a)); for(int i=;i<=n;i++) a[i][i]=; } friend JZ operator + (JZ a,JZ b){ JZ c; for(int i=;i<=n;i++) for(int j=;j<=n;j++) for(int k=;k<=n;k++){ c.a[i][j]+=b.a[i][k]*a.a[k][j]; c.a[i][j]%=; } return c; } }; int ha[maxn]; int main(){ int N,m; while(~scanf("%d%d",&n,&m)&&(m||n)){ memset(ed,,sizeof(ed)); int js1,js2; for(int i=;i<=m;i++){ scanf("%d%d",&js1,&js2); ed[js1+][js2+]=; } int q; scanf("%d",&q); for(int i=;i<=q;i++){ scanf("%d%d%d",&js1,&js2,&N); bool f=; JZ D(,); for(JZ now();N;now=now+now){ if(N&) D=D+now; N>>=;
}
printf("%d\n",D.a[js1+][js2+]);
}
}
return ;
}