How many ways?

?

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2046    Accepted Submission(s): 758

4 4

0 1

0 2

1 3

2 3

2

0 3 2

0 3 3

3 6

0 1

1 0

0 2

2 0

1 2

2 1

2

1 2 1

0 1 3

0 0

2

0

1

3

中文题~

解题思路：经典矩阵算法。把给定的图转为邻接矩阵，即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就可以。

第一道矩阵高速幂。写的比較乱。并且这样的写法时间复杂度较高，没有优化。只是比較easy看懂。

矩阵高速幂预备知识：

①矩阵相乘规则：

矩阵与矩阵相乘 第一个矩阵的列数必须等于第二个矩阵的行数 假如第一个是m*n的矩阵 第二个是n*p的矩阵 则结果就是m*p的矩阵 且得出来的矩阵中元素具有下面特点：

第一行第一列元素为第一个矩阵的第一行的每一个元素和第二个矩阵的第一列的每一个元素乘积的和 以此类推 第i行第j列的元素就是第一个矩阵的第i行的每一个元素与第二个矩阵第j列的每一个元素的乘积的和。

②单位矩阵：

n*n的矩阵  mat ( i , i )=1;  不论什么一个矩阵乘以单位矩阵就是它本身 n*单位矩阵=n， 能够把单位矩阵等价为整数1.

③高速幂：

这里矩阵高速幂等价于整数的高速幂，这里不再具体讲述

上代码：

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

#include <algorithm>

int s[25][25];

int b[25][25];

int n,m;

int a[25][25];

void Mat(int x[25][25],int y[25][25],int modn)

{

	int c[25][25];

	memset(c,0,sizeof(c)); //记得初始化

	for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

			for(int k=0;k<n;k++)

				c[i][j]=(c[i][j]+x[i][k]*y[k][j]%modn)%modn;

	for(int i=0;i<n;i++)

		for(int j=0;j<n;j++)

		x[i][j]=c[i][j];

}

int Matrix(int begin,int end,int k)

{

	for(int i=0;i<n;i++){ //初始化一个单位矩阵

		for(int j=0;j<n;j++){

			a[i][j]=(i==j);

		}

	}

	for(int i=0;i<n;i++){  //记得用s保存再赋给b，不然b值变了之后结果就不正确了

		for(int j=0;j<n;j++){

			b[i][j]=s[i][j];

		}

	}

	while(k){

		if(k&1)Mat(a,b,1000);

		Mat(b,b,1000);

		k>>=1;

	}

	return a[begin][end];

}

int main()

{

	while(scanf("%d%d",&n,&m),n!=0||m!=0){

		int S,G;

		memset(b,0,sizeof(b));

		memset(s,0,sizeof(s));

		for(int i=0;i<m;i++){

			scanf("%d%d",&S,&G);

			s[S][G]=1;

		}

		int T;

		scanf("%d",&T);

		int B,E,k;

		while(T--){

			scanf("%d%d%d",&B,&E,&k);

			int res=Matrix(B,E,k);

			printf("%d\n",res);

		}

	}

	return 0;

}